Um längere Rechnungen zu vermeiden, rechnen wir:

(122 + 15999) mod 4 ≡ (122 mod 4 + 15999 mod 4) mod 4.

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

15999 mod 4 ≡ 3 mod 4 kann man relativ leicht bestimmen, weil ja 15999 = 15000+999 = 4 ⋅ 3750 +999.

Somit gilt:

(122 + 15999) mod 4 ≡ (2 + 3) mod 4 ≡ 5 mod 4 ≡ 1 mod 4.

Um längere Rechnungen zu vermeiden, rechnen wir:

(15 ⋅ 72) mod 6 ≡ (15 mod 6 ⋅ 72 mod 6) mod 6.

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

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

Somit gilt:

(15 ⋅ 72) mod 6 ≡ (3 ⋅ 0) mod 6 ≡ 0 mod 6.

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

2: 142²=142¹⁺¹=142¹⋅142¹ ≡ 142⋅142=20164 ≡ 408 mod 449

4: 142⁴=142²⁺²=142²⋅142² ≡ 408⋅408=166464 ≡ 334 mod 449

8: 142⁸=142⁴⁺⁴=142⁴⋅142⁴ ≡ 334⋅334=111556 ≡ 204 mod 449

16: 142¹⁶=142⁸⁺⁸=142⁸⋅142⁸ ≡ 204⋅204=41616 ≡ 308 mod 449

32: 142³²=142¹⁶⁺¹⁶=142¹⁶⋅142¹⁶ ≡ 308⋅308=94864 ≡ 125 mod 449

64: 142⁶⁴=142³²⁺³²=142³²⋅142³² ≡ 125⋅125=15625 ≡ 359 mod 449

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

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

226 = 128+64+32+2

119²²⁶

= 119^128+64+32+2

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

≡ 54 ⋅ 190 ⋅ 204 ⋅ 173 mod 269
≡ 10260 ⋅ 204 ⋅ 173 mod 269 ≡ 38 ⋅ 204 ⋅ 173 mod 269
≡ 7752 ⋅ 173 mod 269 ≡ 220 ⋅ 173 mod 269
≡ 38060 mod 269 ≡ 131 mod 269

Es gilt also: 119²²⁶ ≡ 131 mod 269

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

=>89	= 1⋅72 + 17
=>72	= 4⋅17 + 4
=>17	= 4⋅4 + 1
=>4	= 4⋅1 + 0

also gilt: ggt(89,72)=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= 17-4⋅4
4= 72-4⋅17	eingesetzt in die Zeile drüber:	1	= 1⋅17 -4⋅(72 -4⋅ 17) = 1⋅17 -4⋅72 +16⋅ 17) = -4⋅72 +17⋅ 17 (=1)
17= 89-1⋅72	eingesetzt in die Zeile drüber:	1	= -4⋅72 +17⋅(89 -1⋅ 72) = -4⋅72 +17⋅89 -17⋅ 72) = 17⋅89 -21⋅ 72 (=1)

Es gilt also: ggt(89,72)=1 = 17⋅89 -21⋅72

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

1 -17⋅89 = -21⋅72

-21⋅72 = -17⋅89 + 1 |+89⋅72

-21⋅72 + 89⋅72 = -17⋅89 + 89⋅72 + 1

(-21 + 89) ⋅ 72 = (-17 + 72) ⋅ 89 + 1

68⋅72 = 55⋅89 + 1

Es gilt also: 68⋅72 = 55⋅89 +1

Somit 68⋅72 = 1 mod 89

68 ist also das Inverse von 72 mod 89