Um längere Rechnungen zu vermeiden, rechnen wir:

(105 - 54) mod 5 ≡ (105 mod 5 - 54 mod 5) mod 5.

105 mod 5 ≡ 0 mod 5 kann man relativ leicht bestimmen, weil ja 105 = 100+5 = 5 ⋅ 20 +5.

54 mod 5 ≡ 4 mod 5 kann man relativ leicht bestimmen, weil ja 54 = 50+4 = 5 ⋅ 10 +4.

Somit gilt:

(105 - 54) mod 5 ≡ (0 - 4) mod 5 ≡ -4 mod 5 ≡ 1 mod 5.

Um längere Rechnungen zu vermeiden, rechnen wir:

(60 ⋅ 29) mod 10 ≡ (60 mod 10 ⋅ 29 mod 10) mod 10.

60 mod 10 ≡ 0 mod 10 kann man relativ leicht bestimmen, weil ja 60 = 60 + 0 = 6 ⋅ 10 + 0 ist.

29 mod 10 ≡ 9 mod 10 kann man relativ leicht bestimmen, weil ja 29 = 20 + 9 = 2 ⋅ 10 + 9 ist.

Somit gilt:

(60 ⋅ 29) mod 10 ≡ (0 ⋅ 9) mod 10 ≡ 0 mod 10.

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

2: 274²=274¹⁺¹=274¹⋅274¹ ≡ 274⋅274=75076 ≡ 275 mod 571

4: 274⁴=274²⁺²=274²⋅274² ≡ 275⋅275=75625 ≡ 253 mod 571

8: 274⁸=274⁴⁺⁴=274⁴⋅274⁴ ≡ 253⋅253=64009 ≡ 57 mod 571

16: 274¹⁶=274⁸⁺⁸=274⁸⋅274⁸ ≡ 57⋅57=3249 ≡ 394 mod 571

32: 274³²=274¹⁶⁺¹⁶=274¹⁶⋅274¹⁶ ≡ 394⋅394=155236 ≡ 495 mod 571

64: 274⁶⁴=274³²⁺³²=274³²⋅274³² ≡ 495⋅495=245025 ≡ 66 mod 571

128: 274¹²⁸=274⁶⁴⁺⁶⁴=274⁶⁴⋅274⁶⁴ ≡ 66⋅66=4356 ≡ 359 mod 571

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

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

121 = 64+32+16+8+1

272¹²¹

= 272^64+32+16+8+1

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

≡ 191 ⋅ 207 ⋅ 255 ⋅ 55 ⋅ 272 mod 277
≡ 39537 ⋅ 255 ⋅ 55 ⋅ 272 mod 277 ≡ 203 ⋅ 255 ⋅ 55 ⋅ 272 mod 277
≡ 51765 ⋅ 55 ⋅ 272 mod 277 ≡ 243 ⋅ 55 ⋅ 272 mod 277
≡ 13365 ⋅ 272 mod 277 ≡ 69 ⋅ 272 mod 277
≡ 18768 mod 277 ≡ 209 mod 277

Es gilt also: 272¹²¹ ≡ 209 mod 277

Berechnung des größten gemeinsamen Teilers von 89 und 83

=>89	= 1⋅83 + 6
=>83	= 13⋅6 + 5
=>6	= 1⋅5 + 1
=>5	= 5⋅1 + 0

also gilt: ggt(89,83)=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= 6-1⋅5
5= 83-13⋅6	eingesetzt in die Zeile drüber:	1	= 1⋅6 -1⋅(83 -13⋅ 6) = 1⋅6 -1⋅83 +13⋅ 6) = -1⋅83 +14⋅ 6 (=1)
6= 89-1⋅83	eingesetzt in die Zeile drüber:	1	= -1⋅83 +14⋅(89 -1⋅ 83) = -1⋅83 +14⋅89 -14⋅ 83) = 14⋅89 -15⋅ 83 (=1)

Es gilt also: ggt(89,83)=1 = 14⋅89 -15⋅83

oder wenn man 14⋅89 auf die linke Seite bringt:

1 -14⋅89 = -15⋅83

-15⋅83 = -14⋅89 + 1 |+89⋅83

-15⋅83 + 89⋅83 = -14⋅89 + 89⋅83 + 1

(-15 + 89) ⋅ 83 = (-14 + 83) ⋅ 89 + 1

74⋅83 = 69⋅89 + 1

Es gilt also: 74⋅83 = 69⋅89 +1

Somit 74⋅83 = 1 mod 89

74 ist also das Inverse von 83 mod 89