Um längere Rechnungen zu vermeiden, rechnen wir:

(140 - 144) mod 7 ≡ (140 mod 7 - 144 mod 7) mod 7.

140 mod 7 ≡ 0 mod 7 kann man relativ leicht bestimmen, weil ja 140 = 140+0 = 7 ⋅ 20 +0.

144 mod 7 ≡ 4 mod 7 kann man relativ leicht bestimmen, weil ja 144 = 140+4 = 7 ⋅ 20 +4.

Somit gilt:

(140 - 144) mod 7 ≡ (0 - 4) mod 7 ≡ -4 mod 7 ≡ 3 mod 7.

Um längere Rechnungen zu vermeiden, rechnen wir:

(70 ⋅ 45) mod 3 ≡ (70 mod 3 ⋅ 45 mod 3) mod 3.

70 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 70 = 69 + 1 = 23 ⋅ 3 + 1 ist.

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

Somit gilt:

(70 ⋅ 45) mod 3 ≡ (1 ⋅ 0) mod 3 ≡ 0 mod 3.

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

2: 657²=657¹⁺¹=657¹⋅657¹ ≡ 657⋅657=431649 ≡ 525 mod 971

4: 657⁴=657²⁺²=657²⋅657² ≡ 525⋅525=275625 ≡ 832 mod 971

8: 657⁸=657⁴⁺⁴=657⁴⋅657⁴ ≡ 832⋅832=692224 ≡ 872 mod 971

16: 657¹⁶=657⁸⁺⁸=657⁸⋅657⁸ ≡ 872⋅872=760384 ≡ 91 mod 971

32: 657³²=657¹⁶⁺¹⁶=657¹⁶⋅657¹⁶ ≡ 91⋅91=8281 ≡ 513 mod 971

64: 657⁶⁴=657³²⁺³²=657³²⋅657³² ≡ 513⋅513=263169 ≡ 28 mod 971

128: 657¹²⁸=657⁶⁴⁺⁶⁴=657⁶⁴⋅657⁶⁴ ≡ 28⋅28=784 ≡ 784 mod 971

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

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

238 = 128+64+32+8+4+2

385²³⁸

= 385^{128+64+32+8+4+2}

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

≡ 697 ⋅ 201 ⋅ 540 ⋅ 322 ⋅ 518 ⋅ 44 mod 709
≡ 140097 ⋅ 540 ⋅ 322 ⋅ 518 ⋅ 44 mod 709 ≡ 424 ⋅ 540 ⋅ 322 ⋅ 518 ⋅ 44 mod 709
≡ 228960 ⋅ 322 ⋅ 518 ⋅ 44 mod 709 ≡ 662 ⋅ 322 ⋅ 518 ⋅ 44 mod 709
≡ 213164 ⋅ 518 ⋅ 44 mod 709 ≡ 464 ⋅ 518 ⋅ 44 mod 709
≡ 240352 ⋅ 44 mod 709 ≡ 1 ⋅ 44 mod 709
≡ 44 mod 709

Es gilt also: 385²³⁸ ≡ 44 mod 709

Berechnung des größten gemeinsamen Teilers von 89 und 84

=>89	= 1⋅84 + 5
=>84	= 16⋅5 + 4
=>5	= 1⋅4 + 1
=>4	= 4⋅1 + 0

also gilt: ggt(89,84)=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-1⋅4
4= 84-16⋅5	eingesetzt in die Zeile drüber:	1	= 1⋅5 -1⋅(84 -16⋅ 5) = 1⋅5 -1⋅84 +16⋅ 5) = -1⋅84 +17⋅ 5 (=1)
5= 89-1⋅84	eingesetzt in die Zeile drüber:	1	= -1⋅84 +17⋅(89 -1⋅ 84) = -1⋅84 +17⋅89 -17⋅ 84) = 17⋅89 -18⋅ 84 (=1)

Es gilt also: ggt(89,84)=1 = 17⋅89 -18⋅84

oder wenn man 17⋅89 auf die linke Seite bringt:

1 -17⋅89 = -18⋅84

-18⋅84 = -17⋅89 + 1 |+89⋅84

-18⋅84 + 89⋅84 = -17⋅89 + 89⋅84 + 1

(-18 + 89) ⋅ 84 = (-17 + 84) ⋅ 89 + 1

71⋅84 = 67⋅89 + 1

Es gilt also: 71⋅84 = 67⋅89 +1

Somit 71⋅84 = 1 mod 89

71 ist also das Inverse von 84 mod 89