Um längere Rechnungen zu vermeiden, rechnen wir:

(237 + 301) mod 6 ≡ (237 mod 6 + 301 mod 6) mod 6.

237 mod 6 ≡ 3 mod 6 kann man relativ leicht bestimmen, weil ja 237 = 240-3 = 6 ⋅ 40 -3 = 6 ⋅ 40 - 6 + 3.

301 mod 6 ≡ 1 mod 6 kann man relativ leicht bestimmen, weil ja 301 = 300+1 = 6 ⋅ 50 +1.

Somit gilt:

(237 + 301) mod 6 ≡ (3 + 1) mod 6 ≡ 4 mod 6.

Um längere Rechnungen zu vermeiden, rechnen wir:

(38 ⋅ 76) mod 9 ≡ (38 mod 9 ⋅ 76 mod 9) mod 9.

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

76 mod 9 ≡ 4 mod 9 kann man relativ leicht bestimmen, weil ja 76 = 72 + 4 = 8 ⋅ 9 + 4 ist.

Somit gilt:

(38 ⋅ 76) mod 9 ≡ (2 ⋅ 4) mod 9 ≡ 8 mod 9.

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

2: 228²=228¹⁺¹=228¹⋅228¹ ≡ 228⋅228=51984 ≡ 70 mod 257

4: 228⁴=228²⁺²=228²⋅228² ≡ 70⋅70=4900 ≡ 17 mod 257

8: 228⁸=228⁴⁺⁴=228⁴⋅228⁴ ≡ 17⋅17=289 ≡ 32 mod 257

16: 228¹⁶=228⁸⁺⁸=228⁸⋅228⁸ ≡ 32⋅32=1024 ≡ 253 mod 257

32: 228³²=228¹⁶⁺¹⁶=228¹⁶⋅228¹⁶ ≡ 253⋅253=64009 ≡ 16 mod 257

64: 228⁶⁴=228³²⁺³²=228³²⋅228³² ≡ 16⋅16=256 ≡ 256 mod 257

128: 228¹²⁸=228⁶⁴⁺⁶⁴=228⁶⁴⋅228⁶⁴ ≡ 256⋅256=65536 ≡ 1 mod 257

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

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

94 = 64+16+8+4+2

364⁹⁴

= 364^64+16+8+4+2

= 364⁶⁴⋅364¹⁶⋅364⁸⋅364⁴⋅364²

≡ 473 ⋅ 410 ⋅ 405 ⋅ 636 ⋅ 82 mod 761
≡ 193930 ⋅ 405 ⋅ 636 ⋅ 82 mod 761 ≡ 636 ⋅ 405 ⋅ 636 ⋅ 82 mod 761
≡ 257580 ⋅ 636 ⋅ 82 mod 761 ≡ 362 ⋅ 636 ⋅ 82 mod 761
≡ 230232 ⋅ 82 mod 761 ≡ 410 ⋅ 82 mod 761
≡ 33620 mod 761 ≡ 136 mod 761

Es gilt also: 364⁹⁴ ≡ 136 mod 761

Berechnung des größten gemeinsamen Teilers von 97 und 90

=>97	= 1⋅90 + 7
=>90	= 12⋅7 + 6
=>7	= 1⋅6 + 1
=>6	= 6⋅1 + 0

also gilt: ggt(97,90)=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= 90-12⋅7	eingesetzt in die Zeile drüber:	1	= 1⋅7 -1⋅(90 -12⋅ 7) = 1⋅7 -1⋅90 +12⋅ 7) = -1⋅90 +13⋅ 7 (=1)
7= 97-1⋅90	eingesetzt in die Zeile drüber:	1	= -1⋅90 +13⋅(97 -1⋅ 90) = -1⋅90 +13⋅97 -13⋅ 90) = 13⋅97 -14⋅ 90 (=1)

Es gilt also: ggt(97,90)=1 = 13⋅97 -14⋅90

oder wenn man 13⋅97 auf die linke Seite bringt:

1 -13⋅97 = -14⋅90

-14⋅90 = -13⋅97 + 1 |+97⋅90

-14⋅90 + 97⋅90 = -13⋅97 + 97⋅90 + 1

(-14 + 97) ⋅ 90 = (-13 + 90) ⋅ 97 + 1

83⋅90 = 77⋅97 + 1

Es gilt also: 83⋅90 = 77⋅97 +1

Somit 83⋅90 = 1 mod 97

83 ist also das Inverse von 90 mod 97