Um längere Rechnungen zu vermeiden, rechnen wir:

(120 - 162) mod 4 ≡ (120 mod 4 - 162 mod 4) mod 4.

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

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

Somit gilt:

(120 - 162) mod 4 ≡ (0 - 2) mod 4 ≡ -2 mod 4 ≡ 2 mod 4.

Um längere Rechnungen zu vermeiden, rechnen wir:

(73 ⋅ 96) mod 10 ≡ (73 mod 10 ⋅ 96 mod 10) mod 10.

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

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

Somit gilt:

(73 ⋅ 96) mod 10 ≡ (3 ⋅ 6) mod 10 ≡ 18 mod 10 ≡ 8 mod 10.

Die 64 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: 426¹=426

2: 426²=426¹⁺¹=426¹⋅426¹ ≡ 426⋅426=181476 ≡ 22 mod 997

4: 426⁴=426²⁺²=426²⋅426² ≡ 22⋅22=484 ≡ 484 mod 997

8: 426⁸=426⁴⁺⁴=426⁴⋅426⁴ ≡ 484⋅484=234256 ≡ 958 mod 997

16: 426¹⁶=426⁸⁺⁸=426⁸⋅426⁸ ≡ 958⋅958=917764 ≡ 524 mod 997

32: 426³²=426¹⁶⁺¹⁶=426¹⁶⋅426¹⁶ ≡ 524⋅524=274576 ≡ 401 mod 997

64: 426⁶⁴=426³²⁺³²=426³²⋅426³² ≡ 401⋅401=160801 ≡ 284 mod 997

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

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

156 = 128+16+8+4

472¹⁵⁶

= 472^128+16+8+4

= 472¹²⁸⋅472¹⁶⋅472⁸⋅472⁴

≡ 647 ⋅ 676 ⋅ 26 ⋅ 59 mod 691
≡ 437372 ⋅ 26 ⋅ 59 mod 691 ≡ 660 ⋅ 26 ⋅ 59 mod 691
≡ 17160 ⋅ 59 mod 691 ≡ 576 ⋅ 59 mod 691
≡ 33984 mod 691 ≡ 125 mod 691

Es gilt also: 472¹⁵⁶ ≡ 125 mod 691

Berechnung des größten gemeinsamen Teilers von 61 und 22

=>61	= 2⋅22 + 17
=>22	= 1⋅17 + 5
=>17	= 3⋅5 + 2
=>5	= 2⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(61,22)=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= 5-2⋅2
2= 17-3⋅5	eingesetzt in die Zeile drüber:	1	= 1⋅5 -2⋅(17 -3⋅ 5) = 1⋅5 -2⋅17 +6⋅ 5) = -2⋅17 +7⋅ 5 (=1)
5= 22-1⋅17	eingesetzt in die Zeile drüber:	1	= -2⋅17 +7⋅(22 -1⋅ 17) = -2⋅17 +7⋅22 -7⋅ 17) = 7⋅22 -9⋅ 17 (=1)
17= 61-2⋅22	eingesetzt in die Zeile drüber:	1	= 7⋅22 -9⋅(61 -2⋅ 22) = 7⋅22 -9⋅61 +18⋅ 22) = -9⋅61 +25⋅ 22 (=1)

Es gilt also: ggt(61,22)=1 = -9⋅61 +25⋅22

oder wenn man -9⋅61 auf die linke Seite bringt:

1 +9⋅61 = +25⋅22

Es gilt also: 25⋅22 = 9⋅61 +1

Somit 25⋅22 = 1 mod 61

25 ist also das Inverse von 22 mod 61