Um längere Rechnungen zu vermeiden, rechnen wir:

(1501 - 19997) mod 5 ≡ (1501 mod 5 - 19997 mod 5) mod 5.

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

19997 mod 5 ≡ 2 mod 5 kann man relativ leicht bestimmen, weil ja 19997 = 19000+997 = 5 ⋅ 3800 +997.

Somit gilt:

(1501 - 19997) mod 5 ≡ (1 - 2) mod 5 ≡ -1 mod 5 ≡ 4 mod 5.

Um längere Rechnungen zu vermeiden, rechnen wir:

(40 ⋅ 17) mod 10 ≡ (40 mod 10 ⋅ 17 mod 10) mod 10.

40 mod 10 ≡ 0 mod 10 kann man relativ leicht bestimmen, weil ja 40 = 40 + 0 = 4 ⋅ 10 + 0 ist.

17 mod 10 ≡ 7 mod 10 kann man relativ leicht bestimmen, weil ja 17 = 10 + 7 = 1 ⋅ 10 + 7 ist.

Somit gilt:

(40 ⋅ 17) mod 10 ≡ (0 ⋅ 7) mod 10 ≡ 0 mod 10.

Die 64 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: 527¹=527

2: 527²=527¹⁺¹=527¹⋅527¹ ≡ 527⋅527=277729 ≡ 887 mod 929

4: 527⁴=527²⁺²=527²⋅527² ≡ 887⋅887=786769 ≡ 835 mod 929

8: 527⁸=527⁴⁺⁴=527⁴⋅527⁴ ≡ 835⋅835=697225 ≡ 475 mod 929

16: 527¹⁶=527⁸⁺⁸=527⁸⋅527⁸ ≡ 475⋅475=225625 ≡ 807 mod 929

32: 527³²=527¹⁶⁺¹⁶=527¹⁶⋅527¹⁶ ≡ 807⋅807=651249 ≡ 20 mod 929

64: 527⁶⁴=527³²⁺³²=527³²⋅527³² ≡ 20⋅20=400 ≡ 400 mod 929

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

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

122 = 64+32+16+8+2

288¹²²

= 288^64+32+16+8+2

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

≡ 48 ⋅ 130 ⋅ 113 ⋅ 304 ⋅ 216 mod 383
≡ 6240 ⋅ 113 ⋅ 304 ⋅ 216 mod 383 ≡ 112 ⋅ 113 ⋅ 304 ⋅ 216 mod 383
≡ 12656 ⋅ 304 ⋅ 216 mod 383 ≡ 17 ⋅ 304 ⋅ 216 mod 383
≡ 5168 ⋅ 216 mod 383 ≡ 189 ⋅ 216 mod 383
≡ 40824 mod 383 ≡ 226 mod 383

Es gilt also: 288¹²² ≡ 226 mod 383

Berechnung des größten gemeinsamen Teilers von 61 und 18

=>61	= 3⋅18 + 7
=>18	= 2⋅7 + 4
=>7	= 1⋅4 + 3
=>4	= 1⋅3 + 1
=>3	= 3⋅1 + 0

also gilt: ggt(61,18)=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= 4-1⋅3
3= 7-1⋅4	eingesetzt in die Zeile drüber:	1	= 1⋅4 -1⋅(7 -1⋅ 4) = 1⋅4 -1⋅7 +1⋅ 4) = -1⋅7 +2⋅ 4 (=1)
4= 18-2⋅7	eingesetzt in die Zeile drüber:	1	= -1⋅7 +2⋅(18 -2⋅ 7) = -1⋅7 +2⋅18 -4⋅ 7) = 2⋅18 -5⋅ 7 (=1)
7= 61-3⋅18	eingesetzt in die Zeile drüber:	1	= 2⋅18 -5⋅(61 -3⋅ 18) = 2⋅18 -5⋅61 +15⋅ 18) = -5⋅61 +17⋅ 18 (=1)

Es gilt also: ggt(61,18)=1 = -5⋅61 +17⋅18

oder wenn man -5⋅61 auf die linke Seite bringt:

1 +5⋅61 = +17⋅18

Es gilt also: 17⋅18 = 5⋅61 +1

Somit 17⋅18 = 1 mod 61

17 ist also das Inverse von 18 mod 61