Um längere Rechnungen zu vermeiden, rechnen wir:

(6006 - 179) mod 6 ≡ (6006 mod 6 - 179 mod 6) mod 6.

6006 mod 6 ≡ 0 mod 6 kann man relativ leicht bestimmen, weil ja 6006 = 6000+6 = 6 ⋅ 1000 +6.

179 mod 6 ≡ 5 mod 6 kann man relativ leicht bestimmen, weil ja 179 = 180-1 = 6 ⋅ 30 -1 = 6 ⋅ 30 - 6 + 5.

Somit gilt:

(6006 - 179) mod 6 ≡ (0 - 5) mod 6 ≡ -5 mod 6 ≡ 1 mod 6.

Um längere Rechnungen zu vermeiden, rechnen wir:

(51 ⋅ 17) mod 7 ≡ (51 mod 7 ⋅ 17 mod 7) mod 7.

51 mod 7 ≡ 2 mod 7 kann man relativ leicht bestimmen, weil ja 51 = 49 + 2 = 7 ⋅ 7 + 2 ist.

17 mod 7 ≡ 3 mod 7 kann man relativ leicht bestimmen, weil ja 17 = 14 + 3 = 2 ⋅ 7 + 3 ist.

Somit gilt:

(51 ⋅ 17) mod 7 ≡ (2 ⋅ 3) mod 7 ≡ 6 mod 7.

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

2: 223²=223¹⁺¹=223¹⋅223¹ ≡ 223⋅223=49729 ≡ 275 mod 313

4: 223⁴=223²⁺²=223²⋅223² ≡ 275⋅275=75625 ≡ 192 mod 313

8: 223⁸=223⁴⁺⁴=223⁴⋅223⁴ ≡ 192⋅192=36864 ≡ 243 mod 313

16: 223¹⁶=223⁸⁺⁸=223⁸⋅223⁸ ≡ 243⋅243=59049 ≡ 205 mod 313

32: 223³²=223¹⁶⁺¹⁶=223¹⁶⋅223¹⁶ ≡ 205⋅205=42025 ≡ 83 mod 313

64: 223⁶⁴=223³²⁺³²=223³²⋅223³² ≡ 83⋅83=6889 ≡ 3 mod 313

128: 223¹²⁸=223⁶⁴⁺⁶⁴=223⁶⁴⋅223⁶⁴ ≡ 3⋅3=9 ≡ 9 mod 313

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

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

119 = 64+32+16+4+2+1

228¹¹⁹

= 228^{64+32+16+4+2+1}

= 228⁶⁴⋅228³²⋅228¹⁶⋅228⁴⋅228²⋅228¹

≡ 327 ⋅ 158 ⋅ 131 ⋅ 192 ⋅ 281 ⋅ 228 mod 347
≡ 51666 ⋅ 131 ⋅ 192 ⋅ 281 ⋅ 228 mod 347 ≡ 310 ⋅ 131 ⋅ 192 ⋅ 281 ⋅ 228 mod 347
≡ 40610 ⋅ 192 ⋅ 281 ⋅ 228 mod 347 ≡ 11 ⋅ 192 ⋅ 281 ⋅ 228 mod 347
≡ 2112 ⋅ 281 ⋅ 228 mod 347 ≡ 30 ⋅ 281 ⋅ 228 mod 347
≡ 8430 ⋅ 228 mod 347 ≡ 102 ⋅ 228 mod 347
≡ 23256 mod 347 ≡ 7 mod 347

Es gilt also: 228¹¹⁹ ≡ 7 mod 347

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

=>73	= 1⋅50 + 23
=>50	= 2⋅23 + 4
=>23	= 5⋅4 + 3
=>4	= 1⋅3 + 1
=>3	= 3⋅1 + 0

also gilt: ggt(73,50)=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= 4-1⋅3
3= 23-5⋅4	eingesetzt in die Zeile drüber:	1	= 1⋅4 -1⋅(23 -5⋅ 4) = 1⋅4 -1⋅23 +5⋅ 4) = -1⋅23 +6⋅ 4 (=1)
4= 50-2⋅23	eingesetzt in die Zeile drüber:	1	= -1⋅23 +6⋅(50 -2⋅ 23) = -1⋅23 +6⋅50 -12⋅ 23) = 6⋅50 -13⋅ 23 (=1)
23= 73-1⋅50	eingesetzt in die Zeile drüber:	1	= 6⋅50 -13⋅(73 -1⋅ 50) = 6⋅50 -13⋅73 +13⋅ 50) = -13⋅73 +19⋅ 50 (=1)

Es gilt also: ggt(73,50)=1 = -13⋅73 +19⋅50

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

1 +13⋅73 = +19⋅50

Es gilt also: 19⋅50 = 13⋅73 +1

Somit 19⋅50 = 1 mod 73

19 ist also das Inverse von 50 mod 73