Um längere Rechnungen zu vermeiden, rechnen wir:

(57 - 11998) mod 6 ≡ (57 mod 6 - 11998 mod 6) mod 6.

57 mod 6 ≡ 3 mod 6 kann man relativ leicht bestimmen, weil ja 57 = 60-3 = 6 ⋅ 10 -3 = 6 ⋅ 10 - 6 + 3.

11998 mod 6 ≡ 4 mod 6 kann man relativ leicht bestimmen, weil ja 11998 = 12000-2 = 6 ⋅ 2000 -2 = 6 ⋅ 2000 - 6 + 4.

Somit gilt:

(57 - 11998) mod 6 ≡ (3 - 4) mod 6 ≡ -1 mod 6 ≡ 5 mod 6.

Um längere Rechnungen zu vermeiden, rechnen wir:

(41 ⋅ 46) mod 11 ≡ (41 mod 11 ⋅ 46 mod 11) mod 11.

41 mod 11 ≡ 8 mod 11 kann man relativ leicht bestimmen, weil ja 41 = 33 + 8 = 3 ⋅ 11 + 8 ist.

46 mod 11 ≡ 2 mod 11 kann man relativ leicht bestimmen, weil ja 46 = 44 + 2 = 4 ⋅ 11 + 2 ist.

Somit gilt:

(41 ⋅ 46) mod 11 ≡ (8 ⋅ 2) mod 11 ≡ 16 mod 11 ≡ 5 mod 11.

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

2: 329²=329¹⁺¹=329¹⋅329¹ ≡ 329⋅329=108241 ≡ 99 mod 389

4: 329⁴=329²⁺²=329²⋅329² ≡ 99⋅99=9801 ≡ 76 mod 389

8: 329⁸=329⁴⁺⁴=329⁴⋅329⁴ ≡ 76⋅76=5776 ≡ 330 mod 389

16: 329¹⁶=329⁸⁺⁸=329⁸⋅329⁸ ≡ 330⋅330=108900 ≡ 369 mod 389

32: 329³²=329¹⁶⁺¹⁶=329¹⁶⋅329¹⁶ ≡ 369⋅369=136161 ≡ 11 mod 389

64: 329⁶⁴=329³²⁺³²=329³²⋅329³² ≡ 11⋅11=121 ≡ 121 mod 389

128: 329¹²⁸=329⁶⁴⁺⁶⁴=329⁶⁴⋅329⁶⁴ ≡ 121⋅121=14641 ≡ 248 mod 389

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

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

245 = 128+64+32+16+4+1

204²⁴⁵

= 204^{128+64+32+16+4+1}

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

≡ 256 ⋅ 241 ⋅ 64 ⋅ 8 ⋅ 67 ⋅ 204 mod 257
≡ 61696 ⋅ 64 ⋅ 8 ⋅ 67 ⋅ 204 mod 257 ≡ 16 ⋅ 64 ⋅ 8 ⋅ 67 ⋅ 204 mod 257
≡ 1024 ⋅ 8 ⋅ 67 ⋅ 204 mod 257 ≡ 253 ⋅ 8 ⋅ 67 ⋅ 204 mod 257
≡ 2024 ⋅ 67 ⋅ 204 mod 257 ≡ 225 ⋅ 67 ⋅ 204 mod 257
≡ 15075 ⋅ 204 mod 257 ≡ 169 ⋅ 204 mod 257
≡ 34476 mod 257 ≡ 38 mod 257

Es gilt also: 204²⁴⁵ ≡ 38 mod 257

Berechnung des größten gemeinsamen Teilers von 73 und 31

=>73	= 2⋅31 + 11
=>31	= 2⋅11 + 9
=>11	= 1⋅9 + 2
=>9	= 4⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(73,31)=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-4⋅2
2= 11-1⋅9	eingesetzt in die Zeile drüber:	1	= 1⋅9 -4⋅(11 -1⋅ 9) = 1⋅9 -4⋅11 +4⋅ 9) = -4⋅11 +5⋅ 9 (=1)
9= 31-2⋅11	eingesetzt in die Zeile drüber:	1	= -4⋅11 +5⋅(31 -2⋅ 11) = -4⋅11 +5⋅31 -10⋅ 11) = 5⋅31 -14⋅ 11 (=1)
11= 73-2⋅31	eingesetzt in die Zeile drüber:	1	= 5⋅31 -14⋅(73 -2⋅ 31) = 5⋅31 -14⋅73 +28⋅ 31) = -14⋅73 +33⋅ 31 (=1)

Es gilt also: ggt(73,31)=1 = -14⋅73 +33⋅31

oder wenn man -14⋅73 auf die linke Seite bringt:

1 +14⋅73 = +33⋅31

Es gilt also: 33⋅31 = 14⋅73 +1

Somit 33⋅31 = 1 mod 73

33 ist also das Inverse von 31 mod 73