Um längere Rechnungen zu vermeiden, rechnen wir:

(19997 - 800) mod 4 ≡ (19997 mod 4 - 800 mod 4) mod 4.

19997 mod 4 ≡ 1 mod 4 kann man relativ leicht bestimmen, weil ja 19997 = 19000+997 = 4 ⋅ 4750 +997.

800 mod 4 ≡ 0 mod 4 kann man relativ leicht bestimmen, weil ja 800 = 800+0 = 4 ⋅ 200 +0.

Somit gilt:

(19997 - 800) mod 4 ≡ (1 - 0) mod 4 ≡ 1 mod 4.

Um längere Rechnungen zu vermeiden, rechnen wir:

(98 ⋅ 15) mod 4 ≡ (98 mod 4 ⋅ 15 mod 4) mod 4.

98 mod 4 ≡ 2 mod 4 kann man relativ leicht bestimmen, weil ja 98 = 96 + 2 = 24 ⋅ 4 + 2 ist.

15 mod 4 ≡ 3 mod 4 kann man relativ leicht bestimmen, weil ja 15 = 12 + 3 = 3 ⋅ 4 + 3 ist.

Somit gilt:

(98 ⋅ 15) mod 4 ≡ (2 ⋅ 3) mod 4 ≡ 6 mod 4 ≡ 2 mod 4.

Die 128 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: 557¹=557

2: 557²=557¹⁺¹=557¹⋅557¹ ≡ 557⋅557=310249 ≡ 604 mod 983

4: 557⁴=557²⁺²=557²⋅557² ≡ 604⋅604=364816 ≡ 123 mod 983

8: 557⁸=557⁴⁺⁴=557⁴⋅557⁴ ≡ 123⋅123=15129 ≡ 384 mod 983

16: 557¹⁶=557⁸⁺⁸=557⁸⋅557⁸ ≡ 384⋅384=147456 ≡ 6 mod 983

32: 557³²=557¹⁶⁺¹⁶=557¹⁶⋅557¹⁶ ≡ 6⋅6=36 ≡ 36 mod 983

64: 557⁶⁴=557³²⁺³²=557³²⋅557³² ≡ 36⋅36=1296 ≡ 313 mod 983

128: 557¹²⁸=557⁶⁴⁺⁶⁴=557⁶⁴⋅557⁶⁴ ≡ 313⋅313=97969 ≡ 652 mod 983

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

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

94 = 64+16+8+4+2

458⁹⁴

= 458^64+16+8+4+2

= 458⁶⁴⋅458¹⁶⋅458⁸⋅458⁴⋅458²

≡ 338 ⋅ 6 ⋅ 49 ⋅ 7 ⋅ 441 mod 479
≡ 2028 ⋅ 49 ⋅ 7 ⋅ 441 mod 479 ≡ 112 ⋅ 49 ⋅ 7 ⋅ 441 mod 479
≡ 5488 ⋅ 7 ⋅ 441 mod 479 ≡ 219 ⋅ 7 ⋅ 441 mod 479
≡ 1533 ⋅ 441 mod 479 ≡ 96 ⋅ 441 mod 479
≡ 42336 mod 479 ≡ 184 mod 479

Es gilt also: 458⁹⁴ ≡ 184 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