Um längere Rechnungen zu vermeiden, rechnen wir:

(20000 - 120) mod 4 ≡ (20000 mod 4 - 120 mod 4) mod 4.

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

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

Somit gilt:

(20000 - 120) mod 4 ≡ (0 - 0) mod 4 ≡ 0 mod 4.

Um längere Rechnungen zu vermeiden, rechnen wir:

(49 ⋅ 74) mod 5 ≡ (49 mod 5 ⋅ 74 mod 5) mod 5.

49 mod 5 ≡ 4 mod 5 kann man relativ leicht bestimmen, weil ja 49 = 45 + 4 = 9 ⋅ 5 + 4 ist.

74 mod 5 ≡ 4 mod 5 kann man relativ leicht bestimmen, weil ja 74 = 70 + 4 = 14 ⋅ 5 + 4 ist.

Somit gilt:

(49 ⋅ 74) mod 5 ≡ (4 ⋅ 4) mod 5 ≡ 16 mod 5 ≡ 1 mod 5.

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: 89¹=89

2: 89²=89¹⁺¹=89¹⋅89¹ ≡ 89⋅89=7921 ≡ 62 mod 271

4: 89⁴=89²⁺²=89²⋅89² ≡ 62⋅62=3844 ≡ 50 mod 271

8: 89⁸=89⁴⁺⁴=89⁴⋅89⁴ ≡ 50⋅50=2500 ≡ 61 mod 271

16: 89¹⁶=89⁸⁺⁸=89⁸⋅89⁸ ≡ 61⋅61=3721 ≡ 198 mod 271

32: 89³²=89¹⁶⁺¹⁶=89¹⁶⋅89¹⁶ ≡ 198⋅198=39204 ≡ 180 mod 271

64: 89⁶⁴=89³²⁺³²=89³²⋅89³² ≡ 180⋅180=32400 ≡ 151 mod 271

128: 89¹²⁸=89⁶⁴⁺⁶⁴=89⁶⁴⋅89⁶⁴ ≡ 151⋅151=22801 ≡ 37 mod 271

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

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

123 = 64+32+16+8+2+1

623¹²³

= 623^{64+32+16+8+2+1}

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

≡ 96 ⋅ 598 ⋅ 193 ⋅ 518 ⋅ 400 ⋅ 623 mod 643
≡ 57408 ⋅ 193 ⋅ 518 ⋅ 400 ⋅ 623 mod 643 ≡ 181 ⋅ 193 ⋅ 518 ⋅ 400 ⋅ 623 mod 643
≡ 34933 ⋅ 518 ⋅ 400 ⋅ 623 mod 643 ≡ 211 ⋅ 518 ⋅ 400 ⋅ 623 mod 643
≡ 109298 ⋅ 400 ⋅ 623 mod 643 ≡ 631 ⋅ 400 ⋅ 623 mod 643
≡ 252400 ⋅ 623 mod 643 ≡ 344 ⋅ 623 mod 643
≡ 214312 mod 643 ≡ 193 mod 643

Es gilt also: 623¹²³ ≡ 193 mod 643

Berechnung des größten gemeinsamen Teilers von 79 und 60

=>79	= 1⋅60 + 19
=>60	= 3⋅19 + 3
=>19	= 6⋅3 + 1
=>3	= 3⋅1 + 0

also gilt: ggt(79,60)=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= 19-6⋅3
3= 60-3⋅19	eingesetzt in die Zeile drüber:	1	= 1⋅19 -6⋅(60 -3⋅ 19) = 1⋅19 -6⋅60 +18⋅ 19) = -6⋅60 +19⋅ 19 (=1)
19= 79-1⋅60	eingesetzt in die Zeile drüber:	1	= -6⋅60 +19⋅(79 -1⋅ 60) = -6⋅60 +19⋅79 -19⋅ 60) = 19⋅79 -25⋅ 60 (=1)

Es gilt also: ggt(79,60)=1 = 19⋅79 -25⋅60

oder wenn man 19⋅79 auf die linke Seite bringt:

1 -19⋅79 = -25⋅60

-25⋅60 = -19⋅79 + 1 |+79⋅60

-25⋅60 + 79⋅60 = -19⋅79 + 79⋅60 + 1

(-25 + 79) ⋅ 60 = (-19 + 60) ⋅ 79 + 1

54⋅60 = 41⋅79 + 1

Es gilt also: 54⋅60 = 41⋅79 +1

Somit 54⋅60 = 1 mod 79

54 ist also das Inverse von 60 mod 79