Um längere Rechnungen zu vermeiden, rechnen wir:

(1197 + 6001) mod 3 ≡ (1197 mod 3 + 6001 mod 3) mod 3.

1197 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 1197 = 1200-3 = 3 ⋅ 400 -3 = 3 ⋅ 400 - 3 + 0.

6001 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 6001 = 6000+1 = 3 ⋅ 2000 +1.

Somit gilt:

(1197 + 6001) mod 3 ≡ (0 + 1) mod 3 ≡ 1 mod 3.

Um längere Rechnungen zu vermeiden, rechnen wir:

(17 ⋅ 50) mod 4 ≡ (17 mod 4 ⋅ 50 mod 4) mod 4.

17 mod 4 ≡ 1 mod 4 kann man relativ leicht bestimmen, weil ja 17 = 16 + 1 = 4 ⋅ 4 + 1 ist.

50 mod 4 ≡ 2 mod 4 kann man relativ leicht bestimmen, weil ja 50 = 48 + 2 = 12 ⋅ 4 + 2 ist.

Somit gilt:

(17 ⋅ 50) mod 4 ≡ (1 ⋅ 2) mod 4 ≡ 2 mod 4.

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

2: 126²=126¹⁺¹=126¹⋅126¹ ≡ 126⋅126=15876 ≡ 26 mod 317

4: 126⁴=126²⁺²=126²⋅126² ≡ 26⋅26=676 ≡ 42 mod 317

8: 126⁸=126⁴⁺⁴=126⁴⋅126⁴ ≡ 42⋅42=1764 ≡ 179 mod 317

16: 126¹⁶=126⁸⁺⁸=126⁸⋅126⁸ ≡ 179⋅179=32041 ≡ 24 mod 317

32: 126³²=126¹⁶⁺¹⁶=126¹⁶⋅126¹⁶ ≡ 24⋅24=576 ≡ 259 mod 317

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

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

207 = 128+64+8+4+2+1

616²⁰⁷

= 616^{128+64+8+4+2+1}

= 616¹²⁸⋅616⁶⁴⋅616⁸⋅616⁴⋅616²⋅616¹

≡ 143 ⋅ 680 ⋅ 100 ⋅ 10 ⋅ 828 ⋅ 616 mod 919
≡ 97240 ⋅ 100 ⋅ 10 ⋅ 828 ⋅ 616 mod 919 ≡ 745 ⋅ 100 ⋅ 10 ⋅ 828 ⋅ 616 mod 919
≡ 74500 ⋅ 10 ⋅ 828 ⋅ 616 mod 919 ≡ 61 ⋅ 10 ⋅ 828 ⋅ 616 mod 919
≡ 610 ⋅ 828 ⋅ 616 mod 919
≡ 505080 ⋅ 616 mod 919 ≡ 549 ⋅ 616 mod 919
≡ 338184 mod 919 ≡ 911 mod 919

Es gilt also: 616²⁰⁷ ≡ 911 mod 919

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