Um längere Rechnungen zu vermeiden, rechnen wir:

(306 - 239) mod 6 ≡ (306 mod 6 - 239 mod 6) mod 6.

306 mod 6 ≡ 0 mod 6 kann man relativ leicht bestimmen, weil ja 306 = 300+6 = 6 ⋅ 50 +6.

239 mod 6 ≡ 5 mod 6 kann man relativ leicht bestimmen, weil ja 239 = 240-1 = 6 ⋅ 40 -1 = 6 ⋅ 40 - 6 + 5.

Somit gilt:

(306 - 239) mod 6 ≡ (0 - 5) mod 6 ≡ -5 mod 6 ≡ 1 mod 6.

Um längere Rechnungen zu vermeiden, rechnen wir:

(52 ⋅ 75) mod 4 ≡ (52 mod 4 ⋅ 75 mod 4) mod 4.

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

75 mod 4 ≡ 3 mod 4 kann man relativ leicht bestimmen, weil ja 75 = 72 + 3 = 18 ⋅ 4 + 3 ist.

Somit gilt:

(52 ⋅ 75) mod 4 ≡ (0 ⋅ 3) mod 4 ≡ 0 mod 4.

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

2: 415²=415¹⁺¹=415¹⋅415¹ ≡ 415⋅415=172225 ≡ 430 mod 881

4: 415⁴=415²⁺²=415²⋅415² ≡ 430⋅430=184900 ≡ 771 mod 881

8: 415⁸=415⁴⁺⁴=415⁴⋅415⁴ ≡ 771⋅771=594441 ≡ 647 mod 881

16: 415¹⁶=415⁸⁺⁸=415⁸⋅415⁸ ≡ 647⋅647=418609 ≡ 134 mod 881

32: 415³²=415¹⁶⁺¹⁶=415¹⁶⋅415¹⁶ ≡ 134⋅134=17956 ≡ 336 mod 881

64: 415⁶⁴=415³²⁺³²=415³²⋅415³² ≡ 336⋅336=112896 ≡ 128 mod 881

128: 415¹²⁸=415⁶⁴⁺⁶⁴=415⁶⁴⋅415⁶⁴ ≡ 128⋅128=16384 ≡ 526 mod 881

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

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

197 = 128+64+4+1

380¹⁹⁷

= 380^128+64+4+1

= 380¹²⁸⋅380⁶⁴⋅380⁴⋅380¹

≡ 184 ⋅ 306 ⋅ 81 ⋅ 380 mod 383
≡ 56304 ⋅ 81 ⋅ 380 mod 383 ≡ 3 ⋅ 81 ⋅ 380 mod 383
≡ 243 ⋅ 380 mod 383
≡ 92340 mod 383 ≡ 37 mod 383

Es gilt also: 380¹⁹⁷ ≡ 37 mod 383

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

=>73	= 2⋅26 + 21
=>26	= 1⋅21 + 5
=>21	= 4⋅5 + 1
=>5	= 5⋅1 + 0

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

Es gilt also: ggt(73,26)=1 = 5⋅73 -14⋅26

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

1 -5⋅73 = -14⋅26

-14⋅26 = -5⋅73 + 1 |+73⋅26

-14⋅26 + 73⋅26 = -5⋅73 + 73⋅26 + 1

(-14 + 73) ⋅ 26 = (-5 + 26) ⋅ 73 + 1

59⋅26 = 21⋅73 + 1

Es gilt also: 59⋅26 = 21⋅73 +1

Somit 59⋅26 = 1 mod 73

59 ist also das Inverse von 26 mod 73