Um längere Rechnungen zu vermeiden, rechnen wir:

(3204 + 323) mod 8 ≡ (3204 mod 8 + 323 mod 8) mod 8.

3204 mod 8 ≡ 4 mod 8 kann man relativ leicht bestimmen, weil ja 3204 = 3200+4 = 8 ⋅ 400 +4.

323 mod 8 ≡ 3 mod 8 kann man relativ leicht bestimmen, weil ja 323 = 320+3 = 8 ⋅ 40 +3.

Somit gilt:

(3204 + 323) mod 8 ≡ (4 + 3) mod 8 ≡ 7 mod 8.

Um längere Rechnungen zu vermeiden, rechnen wir:

(61 ⋅ 78) mod 4 ≡ (61 mod 4 ⋅ 78 mod 4) mod 4.

61 mod 4 ≡ 1 mod 4 kann man relativ leicht bestimmen, weil ja 61 = 60 + 1 = 15 ⋅ 4 + 1 ist.

78 mod 4 ≡ 2 mod 4 kann man relativ leicht bestimmen, weil ja 78 = 76 + 2 = 19 ⋅ 4 + 2 ist.

Somit gilt:

(61 ⋅ 78) mod 4 ≡ (1 ⋅ 2) mod 4 ≡ 2 mod 4.

Die 16 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: 445¹=445

2: 445²=445¹⁺¹=445¹⋅445¹ ≡ 445⋅445=198025 ≡ 144 mod 457

4: 445⁴=445²⁺²=445²⋅445² ≡ 144⋅144=20736 ≡ 171 mod 457

8: 445⁸=445⁴⁺⁴=445⁴⋅445⁴ ≡ 171⋅171=29241 ≡ 450 mod 457

16: 445¹⁶=445⁸⁺⁸=445⁸⋅445⁸ ≡ 450⋅450=202500 ≡ 49 mod 457

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

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

223 = 128+64+16+8+4+2+1

216²²³

= 216^{128+64+16+8+4+2+1}

= 216¹²⁸⋅216⁶⁴⋅216¹⁶⋅216⁸⋅216⁴⋅216²⋅216¹

≡ 190 ⋅ 204 ⋅ 58 ⋅ 70 ⋅ 173 ⋅ 119 ⋅ 216 mod 269
≡ 38760 ⋅ 58 ⋅ 70 ⋅ 173 ⋅ 119 ⋅ 216 mod 269 ≡ 24 ⋅ 58 ⋅ 70 ⋅ 173 ⋅ 119 ⋅ 216 mod 269
≡ 1392 ⋅ 70 ⋅ 173 ⋅ 119 ⋅ 216 mod 269 ≡ 47 ⋅ 70 ⋅ 173 ⋅ 119 ⋅ 216 mod 269
≡ 3290 ⋅ 173 ⋅ 119 ⋅ 216 mod 269 ≡ 62 ⋅ 173 ⋅ 119 ⋅ 216 mod 269
≡ 10726 ⋅ 119 ⋅ 216 mod 269 ≡ 235 ⋅ 119 ⋅ 216 mod 269
≡ 27965 ⋅ 216 mod 269 ≡ 258 ⋅ 216 mod 269
≡ 55728 mod 269 ≡ 45 mod 269

Es gilt also: 216²²³ ≡ 45 mod 269

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

=>89	= 1⋅47 + 42
=>47	= 1⋅42 + 5
=>42	= 8⋅5 + 2
=>5	= 2⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(89,47)=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= 5-2⋅2
2= 42-8⋅5	eingesetzt in die Zeile drüber:	1	= 1⋅5 -2⋅(42 -8⋅ 5) = 1⋅5 -2⋅42 +16⋅ 5) = -2⋅42 +17⋅ 5 (=1)
5= 47-1⋅42	eingesetzt in die Zeile drüber:	1	= -2⋅42 +17⋅(47 -1⋅ 42) = -2⋅42 +17⋅47 -17⋅ 42) = 17⋅47 -19⋅ 42 (=1)
42= 89-1⋅47	eingesetzt in die Zeile drüber:	1	= 17⋅47 -19⋅(89 -1⋅ 47) = 17⋅47 -19⋅89 +19⋅ 47) = -19⋅89 +36⋅ 47 (=1)

Es gilt also: ggt(89,47)=1 = -19⋅89 +36⋅47

oder wenn man -19⋅89 auf die linke Seite bringt:

1 +19⋅89 = +36⋅47

Es gilt also: 36⋅47 = 19⋅89 +1

Somit 36⋅47 = 1 mod 89

36 ist also das Inverse von 47 mod 89