Um längere Rechnungen zu vermeiden, rechnen wir:

(14997 - 602) mod 3 ≡ (14997 mod 3 - 602 mod 3) mod 3.

14997 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 14997 = 15000-3 = 3 ⋅ 5000 -3 = 3 ⋅ 5000 - 3 + 0.

602 mod 3 ≡ 2 mod 3 kann man relativ leicht bestimmen, weil ja 602 = 600+2 = 3 ⋅ 200 +2.

Somit gilt:

(14997 - 602) mod 3 ≡ (0 - 2) mod 3 ≡ -2 mod 3 ≡ 1 mod 3.

Um längere Rechnungen zu vermeiden, rechnen wir:

(32 ⋅ 85) mod 11 ≡ (32 mod 11 ⋅ 85 mod 11) mod 11.

32 mod 11 ≡ 10 mod 11 kann man relativ leicht bestimmen, weil ja 32 = 22 + 10 = 2 ⋅ 11 + 10 ist.

85 mod 11 ≡ 8 mod 11 kann man relativ leicht bestimmen, weil ja 85 = 77 + 8 = 7 ⋅ 11 + 8 ist.

Somit gilt:

(32 ⋅ 85) mod 11 ≡ (10 ⋅ 8) mod 11 ≡ 80 mod 11 ≡ 3 mod 11.

Die 64 im Exponent ist ja ein reine 2er-Potenz (2⁶).

Deswegen quadrieren wir einfach mit jedem Schritt das Ergebnis und kommen so immer eine 2er-Potenz im Exponenten höher:

1: 297¹=297

2: 297²=297¹⁺¹=297¹⋅297¹ ≡ 297⋅297=88209 ≡ 114 mod 839

4: 297⁴=297²⁺²=297²⋅297² ≡ 114⋅114=12996 ≡ 411 mod 839

8: 297⁸=297⁴⁺⁴=297⁴⋅297⁴ ≡ 411⋅411=168921 ≡ 282 mod 839

16: 297¹⁶=297⁸⁺⁸=297⁸⋅297⁸ ≡ 282⋅282=79524 ≡ 658 mod 839

32: 297³²=297¹⁶⁺¹⁶=297¹⁶⋅297¹⁶ ≡ 658⋅658=432964 ≡ 40 mod 839

64: 297⁶⁴=297³²⁺³²=297³²⋅297³² ≡ 40⋅40=1600 ≡ 761 mod 839

Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 227 (grauer Kasten).

Dann schauen wir die Binärdarstellung von 227 an und zerlegen 227 in eine Summer von 2er-Potenzen:

227 = 128+64+32+2+1

243²²⁷

= 243^{128+64+32+2+1}

= 243¹²⁸⋅243⁶⁴⋅243³²⋅243²⋅243¹

≡ 88 ⋅ 137 ⋅ 63 ⋅ 132 ⋅ 243 mod 479
≡ 12056 ⋅ 63 ⋅ 132 ⋅ 243 mod 479 ≡ 81 ⋅ 63 ⋅ 132 ⋅ 243 mod 479
≡ 5103 ⋅ 132 ⋅ 243 mod 479 ≡ 313 ⋅ 132 ⋅ 243 mod 479
≡ 41316 ⋅ 243 mod 479 ≡ 122 ⋅ 243 mod 479
≡ 29646 mod 479 ≡ 427 mod 479

Es gilt also: 243²²⁷ ≡ 427 mod 479

Berechnung des größten gemeinsamen Teilers von 71 und 62

=>71	= 1⋅62 + 9
=>62	= 6⋅9 + 8
=>9	= 1⋅8 + 1
=>8	= 8⋅1 + 0

also gilt: ggt(71,62)=1

Jetzt formen wir jede Zeile von unten nach oben um indem wir das Prokukt auf die andere Seite bringen.
Wir starten mit der zweitletzten Zeile:

1= 9-1⋅8
8= 62-6⋅9	eingesetzt in die Zeile drüber:	1	= 1⋅9 -1⋅(62 -6⋅ 9) = 1⋅9 -1⋅62 +6⋅ 9) = -1⋅62 +7⋅ 9 (=1)
9= 71-1⋅62	eingesetzt in die Zeile drüber:	1	= -1⋅62 +7⋅(71 -1⋅ 62) = -1⋅62 +7⋅71 -7⋅ 62) = 7⋅71 -8⋅ 62 (=1)

Es gilt also: ggt(71,62)=1 = 7⋅71 -8⋅62

oder wenn man 7⋅71 auf die linke Seite bringt:

1 -7⋅71 = -8⋅62

-8⋅62 = -7⋅71 + 1 |+71⋅62

-8⋅62 + 71⋅62 = -7⋅71 + 71⋅62 + 1

(-8 + 71) ⋅ 62 = (-7 + 62) ⋅ 71 + 1

63⋅62 = 55⋅71 + 1

Es gilt also: 63⋅62 = 55⋅71 +1

Somit 63⋅62 = 1 mod 71

63 ist also das Inverse von 62 mod 71