Um längere Rechnungen zu vermeiden, rechnen wir:

(400 + 320) mod 8 ≡ (400 mod 8 + 320 mod 8) mod 8.

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

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

Somit gilt:

(400 + 320) mod 8 ≡ (0 + 0) mod 8 ≡ 0 mod 8.

Um längere Rechnungen zu vermeiden, rechnen wir:

(24 ⋅ 93) mod 8 ≡ (24 mod 8 ⋅ 93 mod 8) mod 8.

24 mod 8 ≡ 0 mod 8 kann man relativ leicht bestimmen, weil ja 24 = 24 + 0 = 3 ⋅ 8 + 0 ist.

93 mod 8 ≡ 5 mod 8 kann man relativ leicht bestimmen, weil ja 93 = 88 + 5 = 11 ⋅ 8 + 5 ist.

Somit gilt:

(24 ⋅ 93) mod 8 ≡ (0 ⋅ 5) mod 8 ≡ 0 mod 8.

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

2: 532²=532¹⁺¹=532¹⋅532¹ ≡ 532⋅532=283024 ≡ 231 mod 569

4: 532⁴=532²⁺²=532²⋅532² ≡ 231⋅231=53361 ≡ 444 mod 569

8: 532⁸=532⁴⁺⁴=532⁴⋅532⁴ ≡ 444⋅444=197136 ≡ 262 mod 569

16: 532¹⁶=532⁸⁺⁸=532⁸⋅532⁸ ≡ 262⋅262=68644 ≡ 364 mod 569

32: 532³²=532¹⁶⁺¹⁶=532¹⁶⋅532¹⁶ ≡ 364⋅364=132496 ≡ 488 mod 569

64: 532⁶⁴=532³²⁺³²=532³²⋅532³² ≡ 488⋅488=238144 ≡ 302 mod 569

128: 532¹²⁸=532⁶⁴⁺⁶⁴=532⁶⁴⋅532⁶⁴ ≡ 302⋅302=91204 ≡ 164 mod 569

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

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

218 = 128+64+16+8+2

206²¹⁸

= 206^{128+64+16+8+2}

= 206¹²⁸⋅206⁶⁴⋅206¹⁶⋅206⁸⋅206²

≡ 474 ⋅ 467 ⋅ 441 ⋅ 592 ⋅ 139 mod 613
≡ 221358 ⋅ 441 ⋅ 592 ⋅ 139 mod 613 ≡ 65 ⋅ 441 ⋅ 592 ⋅ 139 mod 613
≡ 28665 ⋅ 592 ⋅ 139 mod 613 ≡ 467 ⋅ 592 ⋅ 139 mod 613
≡ 276464 ⋅ 139 mod 613 ≡ 1 ⋅ 139 mod 613
≡ 139 mod 613

Es gilt also: 206²¹⁸ ≡ 139 mod 613

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

=>89	= 1⋅46 + 43
=>46	= 1⋅43 + 3
=>43	= 14⋅3 + 1
=>3	= 3⋅1 + 0

also gilt: ggt(89,46)=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= 43-14⋅3
3= 46-1⋅43	eingesetzt in die Zeile drüber:	1	= 1⋅43 -14⋅(46 -1⋅ 43) = 1⋅43 -14⋅46 +14⋅ 43) = -14⋅46 +15⋅ 43 (=1)
43= 89-1⋅46	eingesetzt in die Zeile drüber:	1	= -14⋅46 +15⋅(89 -1⋅ 46) = -14⋅46 +15⋅89 -15⋅ 46) = 15⋅89 -29⋅ 46 (=1)

Es gilt also: ggt(89,46)=1 = 15⋅89 -29⋅46

oder wenn man 15⋅89 auf die linke Seite bringt:

1 -15⋅89 = -29⋅46

-29⋅46 = -15⋅89 + 1 |+89⋅46

-29⋅46 + 89⋅46 = -15⋅89 + 89⋅46 + 1

(-29 + 89) ⋅ 46 = (-15 + 46) ⋅ 89 + 1

60⋅46 = 31⋅89 + 1

Es gilt also: 60⋅46 = 31⋅89 +1

Somit 60⋅46 = 1 mod 89

60 ist also das Inverse von 46 mod 89