Um längere Rechnungen zu vermeiden, rechnen wir:

(27 - 27) mod 3 ≡ (27 mod 3 - 27 mod 3) mod 3.

27 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 27 = 30-3 = 3 ⋅ 10 -3 = 3 ⋅ 10 - 3 + 0.

27 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 27 = 30-3 = 3 ⋅ 10 -3 = 3 ⋅ 10 - 3 + 0.

Somit gilt:

(27 - 27) mod 3 ≡ (0 - 0) mod 3 ≡ 0 mod 3.

Um längere Rechnungen zu vermeiden, rechnen wir:

(71 ⋅ 97) mod 8 ≡ (71 mod 8 ⋅ 97 mod 8) mod 8.

71 mod 8 ≡ 7 mod 8 kann man relativ leicht bestimmen, weil ja 71 = 64 + 7 = 8 ⋅ 8 + 7 ist.

97 mod 8 ≡ 1 mod 8 kann man relativ leicht bestimmen, weil ja 97 = 96 + 1 = 12 ⋅ 8 + 1 ist.

Somit gilt:

(71 ⋅ 97) mod 8 ≡ (7 ⋅ 1) mod 8 ≡ 7 mod 8.

Die 32 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: 237¹=237

2: 237²=237¹⁺¹=237¹⋅237¹ ≡ 237⋅237=56169 ≡ 459 mod 619

4: 237⁴=237²⁺²=237²⋅237² ≡ 459⋅459=210681 ≡ 221 mod 619

8: 237⁸=237⁴⁺⁴=237⁴⋅237⁴ ≡ 221⋅221=48841 ≡ 559 mod 619

16: 237¹⁶=237⁸⁺⁸=237⁸⋅237⁸ ≡ 559⋅559=312481 ≡ 505 mod 619

32: 237³²=237¹⁶⁺¹⁶=237¹⁶⋅237¹⁶ ≡ 505⋅505=255025 ≡ 616 mod 619

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

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

245 = 128+64+32+16+4+1

505²⁴⁵

= 505^{128+64+32+16+4+1}

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

≡ 614 ⋅ 46 ⋅ 429 ⋅ 344 ⋅ 93 ⋅ 505 mod 751
≡ 28244 ⋅ 429 ⋅ 344 ⋅ 93 ⋅ 505 mod 751 ≡ 457 ⋅ 429 ⋅ 344 ⋅ 93 ⋅ 505 mod 751
≡ 196053 ⋅ 344 ⋅ 93 ⋅ 505 mod 751 ≡ 42 ⋅ 344 ⋅ 93 ⋅ 505 mod 751
≡ 14448 ⋅ 93 ⋅ 505 mod 751 ≡ 179 ⋅ 93 ⋅ 505 mod 751
≡ 16647 ⋅ 505 mod 751 ≡ 125 ⋅ 505 mod 751
≡ 63125 mod 751 ≡ 41 mod 751

Es gilt also: 505²⁴⁵ ≡ 41 mod 751

Berechnung des größten gemeinsamen Teilers von 71 und 65

=>71	= 1⋅65 + 6
=>65	= 10⋅6 + 5
=>6	= 1⋅5 + 1
=>5	= 5⋅1 + 0

also gilt: ggt(71,65)=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= 6-1⋅5
5= 65-10⋅6	eingesetzt in die Zeile drüber:	1	= 1⋅6 -1⋅(65 -10⋅ 6) = 1⋅6 -1⋅65 +10⋅ 6) = -1⋅65 +11⋅ 6 (=1)
6= 71-1⋅65	eingesetzt in die Zeile drüber:	1	= -1⋅65 +11⋅(71 -1⋅ 65) = -1⋅65 +11⋅71 -11⋅ 65) = 11⋅71 -12⋅ 65 (=1)

Es gilt also: ggt(71,65)=1 = 11⋅71 -12⋅65

oder wenn man 11⋅71 auf die linke Seite bringt:

1 -11⋅71 = -12⋅65

-12⋅65 = -11⋅71 + 1 |+71⋅65

-12⋅65 + 71⋅65 = -11⋅71 + 71⋅65 + 1

(-12 + 71) ⋅ 65 = (-11 + 65) ⋅ 71 + 1

59⋅65 = 54⋅71 + 1

Es gilt also: 59⋅65 = 54⋅71 +1

Somit 59⋅65 = 1 mod 71

59 ist also das Inverse von 65 mod 71