Um längere Rechnungen zu vermeiden, rechnen wir:

(1502 - 14997) mod 5 ≡ (1502 mod 5 - 14997 mod 5) mod 5.

1502 mod 5 ≡ 2 mod 5 kann man relativ leicht bestimmen, weil ja 1502 = 1500+2 = 5 ⋅ 300 +2.

14997 mod 5 ≡ 2 mod 5 kann man relativ leicht bestimmen, weil ja 14997 = 14000+997 = 5 ⋅ 2800 +997.

Somit gilt:

(1502 - 14997) mod 5 ≡ (2 - 2) mod 5 ≡ 0 mod 5.

Um längere Rechnungen zu vermeiden, rechnen wir:

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

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

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

Somit gilt:

(82 ⋅ 48) 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: 171¹=171

2: 171²=171¹⁺¹=171¹⋅171¹ ≡ 171⋅171=29241 ≡ 65 mod 521

4: 171⁴=171²⁺²=171²⋅171² ≡ 65⋅65=4225 ≡ 57 mod 521

8: 171⁸=171⁴⁺⁴=171⁴⋅171⁴ ≡ 57⋅57=3249 ≡ 123 mod 521

16: 171¹⁶=171⁸⁺⁸=171⁸⋅171⁸ ≡ 123⋅123=15129 ≡ 20 mod 521

32: 171³²=171¹⁶⁺¹⁶=171¹⁶⋅171¹⁶ ≡ 20⋅20=400 ≡ 400 mod 521

64: 171⁶⁴=171³²⁺³²=171³²⋅171³² ≡ 400⋅400=160000 ≡ 53 mod 521

128: 171¹²⁸=171⁶⁴⁺⁶⁴=171⁶⁴⋅171⁶⁴ ≡ 53⋅53=2809 ≡ 204 mod 521

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

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

60 = 32+16+8+4

399⁶⁰

= 399^32+16+8+4

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

≡ 196 ⋅ 453 ⋅ 327 ⋅ 248 mod 467
≡ 88788 ⋅ 327 ⋅ 248 mod 467 ≡ 58 ⋅ 327 ⋅ 248 mod 467
≡ 18966 ⋅ 248 mod 467 ≡ 286 ⋅ 248 mod 467
≡ 70928 mod 467 ≡ 411 mod 467

Es gilt also: 399⁶⁰ ≡ 411 mod 467

Berechnung des größten gemeinsamen Teilers von 83 und 29

=>83	= 2⋅29 + 25
=>29	= 1⋅25 + 4
=>25	= 6⋅4 + 1
=>4	= 4⋅1 + 0

also gilt: ggt(83,29)=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= 25-6⋅4
4= 29-1⋅25	eingesetzt in die Zeile drüber:	1	= 1⋅25 -6⋅(29 -1⋅ 25) = 1⋅25 -6⋅29 +6⋅ 25) = -6⋅29 +7⋅ 25 (=1)
25= 83-2⋅29	eingesetzt in die Zeile drüber:	1	= -6⋅29 +7⋅(83 -2⋅ 29) = -6⋅29 +7⋅83 -14⋅ 29) = 7⋅83 -20⋅ 29 (=1)

Es gilt also: ggt(83,29)=1 = 7⋅83 -20⋅29

oder wenn man 7⋅83 auf die linke Seite bringt:

1 -7⋅83 = -20⋅29

-20⋅29 = -7⋅83 + 1 |+83⋅29

-20⋅29 + 83⋅29 = -7⋅83 + 83⋅29 + 1

(-20 + 83) ⋅ 29 = (-7 + 29) ⋅ 83 + 1

63⋅29 = 22⋅83 + 1

Es gilt also: 63⋅29 = 22⋅83 +1

Somit 63⋅29 = 1 mod 83

63 ist also das Inverse von 29 mod 83