Um längere Rechnungen zu vermeiden, rechnen wir:

(2500 - 20002) mod 5 ≡ (2500 mod 5 - 20002 mod 5) mod 5.

2500 mod 5 ≡ 0 mod 5 kann man relativ leicht bestimmen, weil ja 2500 = 2500+0 = 5 ⋅ 500 +0.

20002 mod 5 ≡ 2 mod 5 kann man relativ leicht bestimmen, weil ja 20002 = 20000+2 = 5 ⋅ 4000 +2.

Somit gilt:

(2500 - 20002) mod 5 ≡ (0 - 2) mod 5 ≡ -2 mod 5 ≡ 3 mod 5.

Um längere Rechnungen zu vermeiden, rechnen wir:

(34 ⋅ 60) mod 11 ≡ (34 mod 11 ⋅ 60 mod 11) mod 11.

34 mod 11 ≡ 1 mod 11 kann man relativ leicht bestimmen, weil ja 34 = 33 + 1 = 3 ⋅ 11 + 1 ist.

60 mod 11 ≡ 5 mod 11 kann man relativ leicht bestimmen, weil ja 60 = 55 + 5 = 5 ⋅ 11 + 5 ist.

Somit gilt:

(34 ⋅ 60) mod 11 ≡ (1 ⋅ 5) mod 11 ≡ 5 mod 11.

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

2: 188²=188¹⁺¹=188¹⋅188¹ ≡ 188⋅188=35344 ≡ 204 mod 251

4: 188⁴=188²⁺²=188²⋅188² ≡ 204⋅204=41616 ≡ 201 mod 251

8: 188⁸=188⁴⁺⁴=188⁴⋅188⁴ ≡ 201⋅201=40401 ≡ 241 mod 251

16: 188¹⁶=188⁸⁺⁸=188⁸⋅188⁸ ≡ 241⋅241=58081 ≡ 100 mod 251

32: 188³²=188¹⁶⁺¹⁶=188¹⁶⋅188¹⁶ ≡ 100⋅100=10000 ≡ 211 mod 251

64: 188⁶⁴=188³²⁺³²=188³²⋅188³² ≡ 211⋅211=44521 ≡ 94 mod 251

128: 188¹²⁸=188⁶⁴⁺⁶⁴=188⁶⁴⋅188⁶⁴ ≡ 94⋅94=8836 ≡ 51 mod 251

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

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

208 = 128+64+16

199²⁰⁸

= 199^128+64+16

= 199¹²⁸⋅199⁶⁴⋅199¹⁶

≡ 163 ⋅ 101 ⋅ 6 mod 239
≡ 16463 ⋅ 6 mod 239 ≡ 211 ⋅ 6 mod 239
≡ 1266 mod 239 ≡ 71 mod 239

Es gilt also: 199²⁰⁸ ≡ 71 mod 239

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

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

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

Es gilt also: ggt(83,54)=1 = -13⋅83 +20⋅54

oder wenn man -13⋅83 auf die linke Seite bringt:

1 +13⋅83 = +20⋅54

Es gilt also: 20⋅54 = 13⋅83 +1

Somit 20⋅54 = 1 mod 83

20 ist also das Inverse von 54 mod 83