Um längere Rechnungen zu vermeiden, rechnen wir:

(1600 + 16000) mod 8 ≡ (1600 mod 8 + 16000 mod 8) mod 8.

1600 mod 8 ≡ 0 mod 8 kann man relativ leicht bestimmen, weil ja 1600 = 1600+0 = 8 ⋅ 200 +0.

16000 mod 8 ≡ 0 mod 8 kann man relativ leicht bestimmen, weil ja 16000 = 16000+0 = 8 ⋅ 2000 +0.

Somit gilt:

(1600 + 16000) mod 8 ≡ (0 + 0) mod 8 ≡ 0 mod 8.

Um längere Rechnungen zu vermeiden, rechnen wir:

(44 ⋅ 70) mod 10 ≡ (44 mod 10 ⋅ 70 mod 10) mod 10.

44 mod 10 ≡ 4 mod 10 kann man relativ leicht bestimmen, weil ja 44 = 40 + 4 = 4 ⋅ 10 + 4 ist.

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

Somit gilt:

(44 ⋅ 70) mod 10 ≡ (4 ⋅ 0) 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: 994¹=994

2: 994²=994¹⁺¹=994¹⋅994¹ ≡ 994⋅994=988036 ≡ 225 mod 1009

4: 994⁴=994²⁺²=994²⋅994² ≡ 225⋅225=50625 ≡ 175 mod 1009

8: 994⁸=994⁴⁺⁴=994⁴⋅994⁴ ≡ 175⋅175=30625 ≡ 355 mod 1009

16: 994¹⁶=994⁸⁺⁸=994⁸⋅994⁸ ≡ 355⋅355=126025 ≡ 909 mod 1009

32: 994³²=994¹⁶⁺¹⁶=994¹⁶⋅994¹⁶ ≡ 909⋅909=826281 ≡ 919 mod 1009

64: 994⁶⁴=994³²⁺³²=994³²⋅994³² ≡ 919⋅919=844561 ≡ 28 mod 1009

128: 994¹²⁸=994⁶⁴⁺⁶⁴=994⁶⁴⋅994⁶⁴ ≡ 28⋅28=784 ≡ 784 mod 1009

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

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

233 = 128+64+32+8+1

429²³³

= 429^{128+64+32+8+1}

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

≡ 141 ⋅ 132 ⋅ 51 ⋅ 548 ⋅ 429 mod 823
≡ 18612 ⋅ 51 ⋅ 548 ⋅ 429 mod 823 ≡ 506 ⋅ 51 ⋅ 548 ⋅ 429 mod 823
≡ 25806 ⋅ 548 ⋅ 429 mod 823 ≡ 293 ⋅ 548 ⋅ 429 mod 823
≡ 160564 ⋅ 429 mod 823 ≡ 79 ⋅ 429 mod 823
≡ 33891 mod 823 ≡ 148 mod 823

Es gilt also: 429²³³ ≡ 148 mod 823

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

=>83	= 1⋅76 + 7
=>76	= 10⋅7 + 6
=>7	= 1⋅6 + 1
=>6	= 6⋅1 + 0

also gilt: ggt(83,76)=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= 7-1⋅6
6= 76-10⋅7	eingesetzt in die Zeile drüber:	1	= 1⋅7 -1⋅(76 -10⋅ 7) = 1⋅7 -1⋅76 +10⋅ 7) = -1⋅76 +11⋅ 7 (=1)
7= 83-1⋅76	eingesetzt in die Zeile drüber:	1	= -1⋅76 +11⋅(83 -1⋅ 76) = -1⋅76 +11⋅83 -11⋅ 76) = 11⋅83 -12⋅ 76 (=1)

Es gilt also: ggt(83,76)=1 = 11⋅83 -12⋅76

oder wenn man 11⋅83 auf die linke Seite bringt:

1 -11⋅83 = -12⋅76

-12⋅76 = -11⋅83 + 1 |+83⋅76

-12⋅76 + 83⋅76 = -11⋅83 + 83⋅76 + 1

(-12 + 83) ⋅ 76 = (-11 + 76) ⋅ 83 + 1

71⋅76 = 65⋅83 + 1

Es gilt also: 71⋅76 = 65⋅83 +1

Somit 71⋅76 = 1 mod 83

71 ist also das Inverse von 76 mod 83