Um längere Rechnungen zu vermeiden, rechnen wir:

(3992 + 324) mod 8 ≡ (3992 mod 8 + 324 mod 8) mod 8.

3992 mod 8 ≡ 0 mod 8 kann man relativ leicht bestimmen, weil ja 3992 = 4000-8 = 8 ⋅ 500 -8 = 8 ⋅ 500 - 8 + 0.

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

Somit gilt:

(3992 + 324) mod 8 ≡ (0 + 4) mod 8 ≡ 4 mod 8.

Um längere Rechnungen zu vermeiden, rechnen wir:

(43 ⋅ 54) mod 9 ≡ (43 mod 9 ⋅ 54 mod 9) mod 9.

43 mod 9 ≡ 7 mod 9 kann man relativ leicht bestimmen, weil ja 43 = 36 + 7 = 4 ⋅ 9 + 7 ist.

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

Somit gilt:

(43 ⋅ 54) mod 9 ≡ (7 ⋅ 0) mod 9 ≡ 0 mod 9.

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

2: 208²=208¹⁺¹=208¹⋅208¹ ≡ 208⋅208=43264 ≡ 35 mod 311

4: 208⁴=208²⁺²=208²⋅208² ≡ 35⋅35=1225 ≡ 292 mod 311

8: 208⁸=208⁴⁺⁴=208⁴⋅208⁴ ≡ 292⋅292=85264 ≡ 50 mod 311

16: 208¹⁶=208⁸⁺⁸=208⁸⋅208⁸ ≡ 50⋅50=2500 ≡ 12 mod 311

32: 208³²=208¹⁶⁺¹⁶=208¹⁶⋅208¹⁶ ≡ 12⋅12=144 ≡ 144 mod 311

64: 208⁶⁴=208³²⁺³²=208³²⋅208³² ≡ 144⋅144=20736 ≡ 210 mod 311

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

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

190 = 128+32+16+8+4+2

567¹⁹⁰

= 567^{128+32+16+8+4+2}

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

≡ 394 ⋅ 609 ⋅ 86 ⋅ 293 ⋅ 407 ⋅ 32 mod 617
≡ 239946 ⋅ 86 ⋅ 293 ⋅ 407 ⋅ 32 mod 617 ≡ 550 ⋅ 86 ⋅ 293 ⋅ 407 ⋅ 32 mod 617
≡ 47300 ⋅ 293 ⋅ 407 ⋅ 32 mod 617 ≡ 408 ⋅ 293 ⋅ 407 ⋅ 32 mod 617
≡ 119544 ⋅ 407 ⋅ 32 mod 617 ≡ 463 ⋅ 407 ⋅ 32 mod 617
≡ 188441 ⋅ 32 mod 617 ≡ 256 ⋅ 32 mod 617
≡ 8192 mod 617 ≡ 171 mod 617

Es gilt also: 567¹⁹⁰ ≡ 171 mod 617

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

=>89	= 1⋅75 + 14
=>75	= 5⋅14 + 5
=>14	= 2⋅5 + 4
=>5	= 1⋅4 + 1
=>4	= 4⋅1 + 0

also gilt: ggt(89,75)=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-1⋅4
4= 14-2⋅5	eingesetzt in die Zeile drüber:	1	= 1⋅5 -1⋅(14 -2⋅ 5) = 1⋅5 -1⋅14 +2⋅ 5) = -1⋅14 +3⋅ 5 (=1)
5= 75-5⋅14	eingesetzt in die Zeile drüber:	1	= -1⋅14 +3⋅(75 -5⋅ 14) = -1⋅14 +3⋅75 -15⋅ 14) = 3⋅75 -16⋅ 14 (=1)
14= 89-1⋅75	eingesetzt in die Zeile drüber:	1	= 3⋅75 -16⋅(89 -1⋅ 75) = 3⋅75 -16⋅89 +16⋅ 75) = -16⋅89 +19⋅ 75 (=1)

Es gilt also: ggt(89,75)=1 = -16⋅89 +19⋅75

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

1 +16⋅89 = +19⋅75

Es gilt also: 19⋅75 = 16⋅89 +1

Somit 19⋅75 = 1 mod 89

19 ist also das Inverse von 75 mod 89