Um längere Rechnungen zu vermeiden, rechnen wir:

(165 + 32005) mod 8 ≡ (165 mod 8 + 32005 mod 8) mod 8.

165 mod 8 ≡ 5 mod 8 kann man relativ leicht bestimmen, weil ja 165 = 160+5 = 8 ⋅ 20 +5.

32005 mod 8 ≡ 5 mod 8 kann man relativ leicht bestimmen, weil ja 32005 = 32000+5 = 8 ⋅ 4000 +5.

Somit gilt:

(165 + 32005) mod 8 ≡ (5 + 5) mod 8 ≡ 10 mod 8 ≡ 2 mod 8.

Um längere Rechnungen zu vermeiden, rechnen wir:

(98 ⋅ 56) mod 8 ≡ (98 mod 8 ⋅ 56 mod 8) mod 8.

98 mod 8 ≡ 2 mod 8 kann man relativ leicht bestimmen, weil ja 98 = 96 + 2 = 12 ⋅ 8 + 2 ist.

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

Somit gilt:

(98 ⋅ 56) mod 8 ≡ (2 ⋅ 0) 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: 403¹=403

2: 403²=403¹⁺¹=403¹⋅403¹ ≡ 403⋅403=162409 ≡ 28 mod 479

4: 403⁴=403²⁺²=403²⋅403² ≡ 28⋅28=784 ≡ 305 mod 479

8: 403⁸=403⁴⁺⁴=403⁴⋅403⁴ ≡ 305⋅305=93025 ≡ 99 mod 479

16: 403¹⁶=403⁸⁺⁸=403⁸⋅403⁸ ≡ 99⋅99=9801 ≡ 221 mod 479

32: 403³²=403¹⁶⁺¹⁶=403¹⁶⋅403¹⁶ ≡ 221⋅221=48841 ≡ 462 mod 479

64: 403⁶⁴=403³²⁺³²=403³²⋅403³² ≡ 462⋅462=213444 ≡ 289 mod 479

128: 403¹²⁸=403⁶⁴⁺⁶⁴=403⁶⁴⋅403⁶⁴ ≡ 289⋅289=83521 ≡ 175 mod 479

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

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

126 = 64+32+16+8+4+2

375¹²⁶

= 375^{64+32+16+8+4+2}

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

≡ 234 ⋅ 69 ⋅ 354 ⋅ 86 ⋅ 452 ⋅ 288 mod 503
≡ 16146 ⋅ 354 ⋅ 86 ⋅ 452 ⋅ 288 mod 503 ≡ 50 ⋅ 354 ⋅ 86 ⋅ 452 ⋅ 288 mod 503
≡ 17700 ⋅ 86 ⋅ 452 ⋅ 288 mod 503 ≡ 95 ⋅ 86 ⋅ 452 ⋅ 288 mod 503
≡ 8170 ⋅ 452 ⋅ 288 mod 503 ≡ 122 ⋅ 452 ⋅ 288 mod 503
≡ 55144 ⋅ 288 mod 503 ≡ 317 ⋅ 288 mod 503
≡ 91296 mod 503 ≡ 253 mod 503

Es gilt also: 375¹²⁶ ≡ 253 mod 503

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

=>89	= 2⋅37 + 15
=>37	= 2⋅15 + 7
=>15	= 2⋅7 + 1
=>7	= 7⋅1 + 0

also gilt: ggt(89,37)=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= 15-2⋅7
7= 37-2⋅15	eingesetzt in die Zeile drüber:	1	= 1⋅15 -2⋅(37 -2⋅ 15) = 1⋅15 -2⋅37 +4⋅ 15) = -2⋅37 +5⋅ 15 (=1)
15= 89-2⋅37	eingesetzt in die Zeile drüber:	1	= -2⋅37 +5⋅(89 -2⋅ 37) = -2⋅37 +5⋅89 -10⋅ 37) = 5⋅89 -12⋅ 37 (=1)

Es gilt also: ggt(89,37)=1 = 5⋅89 -12⋅37

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

1 -5⋅89 = -12⋅37

-12⋅37 = -5⋅89 + 1 |+89⋅37

-12⋅37 + 89⋅37 = -5⋅89 + 89⋅37 + 1

(-12 + 89) ⋅ 37 = (-5 + 37) ⋅ 89 + 1

77⋅37 = 32⋅89 + 1

Es gilt also: 77⋅37 = 32⋅89 +1

Somit 77⋅37 = 1 mod 89

77 ist also das Inverse von 37 mod 89