Um längere Rechnungen zu vermeiden, rechnen wir:

(182 + 123) mod 6 ≡ (182 mod 6 + 123 mod 6) mod 6.

182 mod 6 ≡ 2 mod 6 kann man relativ leicht bestimmen, weil ja 182 = 180+2 = 6 ⋅ 30 +2.

123 mod 6 ≡ 3 mod 6 kann man relativ leicht bestimmen, weil ja 123 = 120+3 = 6 ⋅ 20 +3.

Somit gilt:

(182 + 123) mod 6 ≡ (2 + 3) mod 6 ≡ 5 mod 6.

Um längere Rechnungen zu vermeiden, rechnen wir:

(65 ⋅ 82) mod 8 ≡ (65 mod 8 ⋅ 82 mod 8) mod 8.

65 mod 8 ≡ 1 mod 8 kann man relativ leicht bestimmen, weil ja 65 = 64 + 1 = 8 ⋅ 8 + 1 ist.

82 mod 8 ≡ 2 mod 8 kann man relativ leicht bestimmen, weil ja 82 = 80 + 2 = 10 ⋅ 8 + 2 ist.

Somit gilt:

(65 ⋅ 82) mod 8 ≡ (1 ⋅ 2) mod 8 ≡ 2 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: 237¹=237

2: 237²=237¹⁺¹=237¹⋅237¹ ≡ 237⋅237=56169 ≡ 375 mod 547

4: 237⁴=237²⁺²=237²⋅237² ≡ 375⋅375=140625 ≡ 46 mod 547

8: 237⁸=237⁴⁺⁴=237⁴⋅237⁴ ≡ 46⋅46=2116 ≡ 475 mod 547

16: 237¹⁶=237⁸⁺⁸=237⁸⋅237⁸ ≡ 475⋅475=225625 ≡ 261 mod 547

32: 237³²=237¹⁶⁺¹⁶=237¹⁶⋅237¹⁶ ≡ 261⋅261=68121 ≡ 293 mod 547

64: 237⁶⁴=237³²⁺³²=237³²⋅237³² ≡ 293⋅293=85849 ≡ 517 mod 547

128: 237¹²⁸=237⁶⁴⁺⁶⁴=237⁶⁴⋅237⁶⁴ ≡ 517⋅517=267289 ≡ 353 mod 547

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

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

86 = 64+16+4+2

229⁸⁶

= 229^64+16+4+2

= 229⁶⁴⋅229¹⁶⋅229⁴⋅229²

≡ 237 ⋅ 281 ⋅ 462 ⋅ 198 mod 587
≡ 66597 ⋅ 462 ⋅ 198 mod 587 ≡ 266 ⋅ 462 ⋅ 198 mod 587
≡ 122892 ⋅ 198 mod 587 ≡ 209 ⋅ 198 mod 587
≡ 41382 mod 587 ≡ 292 mod 587

Es gilt also: 229⁸⁶ ≡ 292 mod 587

Berechnung des größten gemeinsamen Teilers von 59 und 31

=>59	= 1⋅31 + 28
=>31	= 1⋅28 + 3
=>28	= 9⋅3 + 1
=>3	= 3⋅1 + 0

also gilt: ggt(59,31)=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= 28-9⋅3
3= 31-1⋅28	eingesetzt in die Zeile drüber:	1	= 1⋅28 -9⋅(31 -1⋅ 28) = 1⋅28 -9⋅31 +9⋅ 28) = -9⋅31 +10⋅ 28 (=1)
28= 59-1⋅31	eingesetzt in die Zeile drüber:	1	= -9⋅31 +10⋅(59 -1⋅ 31) = -9⋅31 +10⋅59 -10⋅ 31) = 10⋅59 -19⋅ 31 (=1)

Es gilt also: ggt(59,31)=1 = 10⋅59 -19⋅31

oder wenn man 10⋅59 auf die linke Seite bringt:

1 -10⋅59 = -19⋅31

-19⋅31 = -10⋅59 + 1 |+59⋅31

-19⋅31 + 59⋅31 = -10⋅59 + 59⋅31 + 1

(-19 + 59) ⋅ 31 = (-10 + 31) ⋅ 59 + 1

40⋅31 = 21⋅59 + 1

Es gilt also: 40⋅31 = 21⋅59 +1

Somit 40⋅31 = 1 mod 59

40 ist also das Inverse von 31 mod 59