Um längere Rechnungen zu vermeiden, rechnen wir:

(600 + 12003) mod 6 ≡ (600 mod 6 + 12003 mod 6) mod 6.

600 mod 6 ≡ 0 mod 6 kann man relativ leicht bestimmen, weil ja 600 = 600+0 = 6 ⋅ 100 +0.

12003 mod 6 ≡ 3 mod 6 kann man relativ leicht bestimmen, weil ja 12003 = 12000+3 = 6 ⋅ 2000 +3.

Somit gilt:

(600 + 12003) mod 6 ≡ (0 + 3) mod 6 ≡ 3 mod 6.

Um längere Rechnungen zu vermeiden, rechnen wir:

(22 ⋅ 73) mod 5 ≡ (22 mod 5 ⋅ 73 mod 5) mod 5.

22 mod 5 ≡ 2 mod 5 kann man relativ leicht bestimmen, weil ja 22 = 20 + 2 = 4 ⋅ 5 + 2 ist.

73 mod 5 ≡ 3 mod 5 kann man relativ leicht bestimmen, weil ja 73 = 70 + 3 = 14 ⋅ 5 + 3 ist.

Somit gilt:

(22 ⋅ 73) mod 5 ≡ (2 ⋅ 3) mod 5 ≡ 6 mod 5 ≡ 1 mod 5.

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

2: 394²=394¹⁺¹=394¹⋅394¹ ≡ 394⋅394=155236 ≡ 131 mod 463

4: 394⁴=394²⁺²=394²⋅394² ≡ 131⋅131=17161 ≡ 30 mod 463

8: 394⁸=394⁴⁺⁴=394⁴⋅394⁴ ≡ 30⋅30=900 ≡ 437 mod 463

16: 394¹⁶=394⁸⁺⁸=394⁸⋅394⁸ ≡ 437⋅437=190969 ≡ 213 mod 463

32: 394³²=394¹⁶⁺¹⁶=394¹⁶⋅394¹⁶ ≡ 213⋅213=45369 ≡ 458 mod 463

64: 394⁶⁴=394³²⁺³²=394³²⋅394³² ≡ 458⋅458=209764 ≡ 25 mod 463

128: 394¹²⁸=394⁶⁴⁺⁶⁴=394⁶⁴⋅394⁶⁴ ≡ 25⋅25=625 ≡ 162 mod 463

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

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

174 = 128+32+8+4+2

261¹⁷⁴

= 261^128+32+8+4+2

= 261¹²⁸⋅261³²⋅261⁸⋅261⁴⋅261²

≡ 211 ⋅ 155 ⋅ 238 ⋅ 111 ⋅ 119 mod 281
≡ 32705 ⋅ 238 ⋅ 111 ⋅ 119 mod 281 ≡ 109 ⋅ 238 ⋅ 111 ⋅ 119 mod 281
≡ 25942 ⋅ 111 ⋅ 119 mod 281 ≡ 90 ⋅ 111 ⋅ 119 mod 281
≡ 9990 ⋅ 119 mod 281 ≡ 155 ⋅ 119 mod 281
≡ 18445 mod 281 ≡ 180 mod 281

Es gilt also: 261¹⁷⁴ ≡ 180 mod 281

Berechnung des größten gemeinsamen Teilers von 101 und 72

=>101	= 1⋅72 + 29
=>72	= 2⋅29 + 14
=>29	= 2⋅14 + 1
=>14	= 14⋅1 + 0

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

Es gilt also: ggt(101,72)=1 = 5⋅101 -7⋅72

oder wenn man 5⋅101 auf die linke Seite bringt:

1 -5⋅101 = -7⋅72

-7⋅72 = -5⋅101 + 1 |+101⋅72

-7⋅72 + 101⋅72 = -5⋅101 + 101⋅72 + 1

(-7 + 101) ⋅ 72 = (-5 + 72) ⋅ 101 + 1

94⋅72 = 67⋅101 + 1

Es gilt also: 94⋅72 = 67⋅101 +1

Somit 94⋅72 = 1 mod 101

94 ist also das Inverse von 72 mod 101