Um längere Rechnungen zu vermeiden, rechnen wir:

(202 - 10001) mod 5 ≡ (202 mod 5 - 10001 mod 5) mod 5.

202 mod 5 ≡ 2 mod 5 kann man relativ leicht bestimmen, weil ja 202 = 200+2 = 5 ⋅ 40 +2.

10001 mod 5 ≡ 1 mod 5 kann man relativ leicht bestimmen, weil ja 10001 = 10000+1 = 5 ⋅ 2000 +1.

Somit gilt:

(202 - 10001) mod 5 ≡ (2 - 1) mod 5 ≡ 1 mod 5.

Um längere Rechnungen zu vermeiden, rechnen wir:

(59 ⋅ 76) mod 3 ≡ (59 mod 3 ⋅ 76 mod 3) mod 3.

59 mod 3 ≡ 2 mod 3 kann man relativ leicht bestimmen, weil ja 59 = 57 + 2 = 19 ⋅ 3 + 2 ist.

76 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 76 = 75 + 1 = 25 ⋅ 3 + 1 ist.

Somit gilt:

(59 ⋅ 76) mod 3 ≡ (2 ⋅ 1) mod 3 ≡ 2 mod 3.

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

2: 386²=386¹⁺¹=386¹⋅386¹ ≡ 386⋅386=148996 ≡ 317 mod 947

4: 386⁴=386²⁺²=386²⋅386² ≡ 317⋅317=100489 ≡ 107 mod 947

8: 386⁸=386⁴⁺⁴=386⁴⋅386⁴ ≡ 107⋅107=11449 ≡ 85 mod 947

16: 386¹⁶=386⁸⁺⁸=386⁸⋅386⁸ ≡ 85⋅85=7225 ≡ 596 mod 947

32: 386³²=386¹⁶⁺¹⁶=386¹⁶⋅386¹⁶ ≡ 596⋅596=355216 ≡ 91 mod 947

64: 386⁶⁴=386³²⁺³²=386³²⋅386³² ≡ 91⋅91=8281 ≡ 705 mod 947

128: 386¹²⁸=386⁶⁴⁺⁶⁴=386⁶⁴⋅386⁶⁴ ≡ 705⋅705=497025 ≡ 797 mod 947

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

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

147 = 128+16+2+1

367¹⁴⁷

= 367^128+16+2+1

= 367¹²⁸⋅367¹⁶⋅367²⋅367¹

≡ 141 ⋅ 244 ⋅ 355 ⋅ 367 mod 439
≡ 34404 ⋅ 355 ⋅ 367 mod 439 ≡ 162 ⋅ 355 ⋅ 367 mod 439
≡ 57510 ⋅ 367 mod 439 ≡ 1 ⋅ 367 mod 439
≡ 367 mod 439

Es gilt also: 367¹⁴⁷ ≡ 367 mod 439

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

=>61	= 1⋅54 + 7
=>54	= 7⋅7 + 5
=>7	= 1⋅5 + 2
=>5	= 2⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(61,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= 5-2⋅2
2= 7-1⋅5	eingesetzt in die Zeile drüber:	1	= 1⋅5 -2⋅(7 -1⋅ 5) = 1⋅5 -2⋅7 +2⋅ 5) = -2⋅7 +3⋅ 5 (=1)
5= 54-7⋅7	eingesetzt in die Zeile drüber:	1	= -2⋅7 +3⋅(54 -7⋅ 7) = -2⋅7 +3⋅54 -21⋅ 7) = 3⋅54 -23⋅ 7 (=1)
7= 61-1⋅54	eingesetzt in die Zeile drüber:	1	= 3⋅54 -23⋅(61 -1⋅ 54) = 3⋅54 -23⋅61 +23⋅ 54) = -23⋅61 +26⋅ 54 (=1)

Es gilt also: ggt(61,54)=1 = -23⋅61 +26⋅54

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

1 +23⋅61 = +26⋅54

Es gilt also: 26⋅54 = 23⋅61 +1

Somit 26⋅54 = 1 mod 61

26 ist also das Inverse von 54 mod 61