Um längere Rechnungen zu vermeiden, rechnen wir:

(160 - 1197) mod 4 ≡ (160 mod 4 - 1197 mod 4) mod 4.

160 mod 4 ≡ 0 mod 4 kann man relativ leicht bestimmen, weil ja 160 = 160+0 = 4 ⋅ 40 +0.

1197 mod 4 ≡ 1 mod 4 kann man relativ leicht bestimmen, weil ja 1197 = 1100+97 = 4 ⋅ 275 +97.

Somit gilt:

(160 - 1197) mod 4 ≡ (0 - 1) mod 4 ≡ -1 mod 4 ≡ 3 mod 4.

Um längere Rechnungen zu vermeiden, rechnen wir:

(27 ⋅ 91) mod 9 ≡ (27 mod 9 ⋅ 91 mod 9) mod 9.

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

91 mod 9 ≡ 1 mod 9 kann man relativ leicht bestimmen, weil ja 91 = 90 + 1 = 10 ⋅ 9 + 1 ist.

Somit gilt:

(27 ⋅ 91) mod 9 ≡ (0 ⋅ 1) mod 9 ≡ 0 mod 9.

Die 16 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: 116¹=116

2: 116²=116¹⁺¹=116¹⋅116¹ ≡ 116⋅116=13456 ≡ 63 mod 227

4: 116⁴=116²⁺²=116²⋅116² ≡ 63⋅63=3969 ≡ 110 mod 227

8: 116⁸=116⁴⁺⁴=116⁴⋅116⁴ ≡ 110⋅110=12100 ≡ 69 mod 227

16: 116¹⁶=116⁸⁺⁸=116⁸⋅116⁸ ≡ 69⋅69=4761 ≡ 221 mod 227

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

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

237 = 128+64+32+8+4+1

501²³⁷

= 501^{128+64+32+8+4+1}

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

≡ 474 ⋅ 764 ⋅ 333 ⋅ 64 ⋅ 8 ⋅ 501 mod 881
≡ 362136 ⋅ 333 ⋅ 64 ⋅ 8 ⋅ 501 mod 881 ≡ 45 ⋅ 333 ⋅ 64 ⋅ 8 ⋅ 501 mod 881
≡ 14985 ⋅ 64 ⋅ 8 ⋅ 501 mod 881 ≡ 8 ⋅ 64 ⋅ 8 ⋅ 501 mod 881
≡ 512 ⋅ 8 ⋅ 501 mod 881
≡ 4096 ⋅ 501 mod 881 ≡ 572 ⋅ 501 mod 881
≡ 286572 mod 881 ≡ 247 mod 881

Es gilt also: 501²³⁷ ≡ 247 mod 881

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