Um längere Rechnungen zu vermeiden, rechnen wir:

(10005 - 5001) mod 5 ≡ (10005 mod 5 - 5001 mod 5) mod 5.

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

5001 mod 5 ≡ 1 mod 5 kann man relativ leicht bestimmen, weil ja 5001 = 5000+1 = 5 ⋅ 1000 +1.

Somit gilt:

(10005 - 5001) mod 5 ≡ (0 - 1) mod 5 ≡ -1 mod 5 ≡ 4 mod 5.

Um längere Rechnungen zu vermeiden, rechnen wir:

(15 ⋅ 58) mod 3 ≡ (15 mod 3 ⋅ 58 mod 3) mod 3.

15 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 15 = 15 + 0 = 5 ⋅ 3 + 0 ist.

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

Somit gilt:

(15 ⋅ 58) mod 3 ≡ (0 ⋅ 1) mod 3 ≡ 0 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: 261¹=261

2: 261²=261¹⁺¹=261¹⋅261¹ ≡ 261⋅261=68121 ≡ 342 mod 443

4: 261⁴=261²⁺²=261²⋅261² ≡ 342⋅342=116964 ≡ 12 mod 443

8: 261⁸=261⁴⁺⁴=261⁴⋅261⁴ ≡ 12⋅12=144 ≡ 144 mod 443

16: 261¹⁶=261⁸⁺⁸=261⁸⋅261⁸ ≡ 144⋅144=20736 ≡ 358 mod 443

32: 261³²=261¹⁶⁺¹⁶=261¹⁶⋅261¹⁶ ≡ 358⋅358=128164 ≡ 137 mod 443

64: 261⁶⁴=261³²⁺³²=261³²⋅261³² ≡ 137⋅137=18769 ≡ 163 mod 443

128: 261¹²⁸=261⁶⁴⁺⁶⁴=261⁶⁴⋅261⁶⁴ ≡ 163⋅163=26569 ≡ 432 mod 443

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

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

234 = 128+64+32+8+2

121²³⁴

= 121^{128+64+32+8+2}

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

≡ 58 ⋅ 110 ⋅ 188 ⋅ 213 ⋅ 146 mod 223
≡ 6380 ⋅ 188 ⋅ 213 ⋅ 146 mod 223 ≡ 136 ⋅ 188 ⋅ 213 ⋅ 146 mod 223
≡ 25568 ⋅ 213 ⋅ 146 mod 223 ≡ 146 ⋅ 213 ⋅ 146 mod 223
≡ 31098 ⋅ 146 mod 223 ≡ 101 ⋅ 146 mod 223
≡ 14746 mod 223 ≡ 28 mod 223

Es gilt also: 121²³⁴ ≡ 28 mod 223

Berechnung des größten gemeinsamen Teilers von 73 und 44

=>73	= 1⋅44 + 29
=>44	= 1⋅29 + 15
=>29	= 1⋅15 + 14
=>15	= 1⋅14 + 1
=>14	= 14⋅1 + 0

also gilt: ggt(73,44)=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-1⋅14
14= 29-1⋅15	eingesetzt in die Zeile drüber:	1	= 1⋅15 -1⋅(29 -1⋅ 15) = 1⋅15 -1⋅29 +1⋅ 15) = -1⋅29 +2⋅ 15 (=1)
15= 44-1⋅29	eingesetzt in die Zeile drüber:	1	= -1⋅29 +2⋅(44 -1⋅ 29) = -1⋅29 +2⋅44 -2⋅ 29) = 2⋅44 -3⋅ 29 (=1)
29= 73-1⋅44	eingesetzt in die Zeile drüber:	1	= 2⋅44 -3⋅(73 -1⋅ 44) = 2⋅44 -3⋅73 +3⋅ 44) = -3⋅73 +5⋅ 44 (=1)

Es gilt also: ggt(73,44)=1 = -3⋅73 +5⋅44

oder wenn man -3⋅73 auf die linke Seite bringt:

1 +3⋅73 = +5⋅44

Es gilt also: 5⋅44 = 3⋅73 +1

Somit 5⋅44 = 1 mod 73

5 ist also das Inverse von 44 mod 73