Um längere Rechnungen zu vermeiden, rechnen wir:

(21006 + 14005) mod 7 ≡ (21006 mod 7 + 14005 mod 7) mod 7.

21006 mod 7 ≡ 6 mod 7 kann man relativ leicht bestimmen, weil ja 21006 = 21000+6 = 7 ⋅ 3000 +6.

14005 mod 7 ≡ 5 mod 7 kann man relativ leicht bestimmen, weil ja 14005 = 14000+5 = 7 ⋅ 2000 +5.

Somit gilt:

(21006 + 14005) mod 7 ≡ (6 + 5) mod 7 ≡ 11 mod 7 ≡ 4 mod 7.

Um längere Rechnungen zu vermeiden, rechnen wir:

(56 ⋅ 49) mod 7 ≡ (56 mod 7 ⋅ 49 mod 7) mod 7.

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

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

Somit gilt:

(56 ⋅ 49) mod 7 ≡ (0 ⋅ 0) mod 7 ≡ 0 mod 7.

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

2: 614²=614¹⁺¹=614¹⋅614¹ ≡ 614⋅614=376996 ≡ 157 mod 821

4: 614⁴=614²⁺²=614²⋅614² ≡ 157⋅157=24649 ≡ 19 mod 821

8: 614⁸=614⁴⁺⁴=614⁴⋅614⁴ ≡ 19⋅19=361 ≡ 361 mod 821

16: 614¹⁶=614⁸⁺⁸=614⁸⋅614⁸ ≡ 361⋅361=130321 ≡ 603 mod 821

32: 614³²=614¹⁶⁺¹⁶=614¹⁶⋅614¹⁶ ≡ 603⋅603=363609 ≡ 727 mod 821

64: 614⁶⁴=614³²⁺³²=614³²⋅614³² ≡ 727⋅727=528529 ≡ 626 mod 821

128: 614¹²⁸=614⁶⁴⁺⁶⁴=614⁶⁴⋅614⁶⁴ ≡ 626⋅626=391876 ≡ 259 mod 821

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

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

236 = 128+64+32+8+4

197²³⁶

= 197^{128+64+32+8+4}

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

≡ 185 ⋅ 140 ⋅ 217 ⋅ 331 ⋅ 88 mod 353
≡ 25900 ⋅ 217 ⋅ 331 ⋅ 88 mod 353 ≡ 131 ⋅ 217 ⋅ 331 ⋅ 88 mod 353
≡ 28427 ⋅ 331 ⋅ 88 mod 353 ≡ 187 ⋅ 331 ⋅ 88 mod 353
≡ 61897 ⋅ 88 mod 353 ≡ 122 ⋅ 88 mod 353
≡ 10736 mod 353 ≡ 146 mod 353

Es gilt also: 197²³⁶ ≡ 146 mod 353

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

=>101	= 1⋅65 + 36
=>65	= 1⋅36 + 29
=>36	= 1⋅29 + 7
=>29	= 4⋅7 + 1
=>7	= 7⋅1 + 0

also gilt: ggt(101,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= 29-4⋅7
7= 36-1⋅29	eingesetzt in die Zeile drüber:	1	= 1⋅29 -4⋅(36 -1⋅ 29) = 1⋅29 -4⋅36 +4⋅ 29) = -4⋅36 +5⋅ 29 (=1)
29= 65-1⋅36	eingesetzt in die Zeile drüber:	1	= -4⋅36 +5⋅(65 -1⋅ 36) = -4⋅36 +5⋅65 -5⋅ 36) = 5⋅65 -9⋅ 36 (=1)
36= 101-1⋅65	eingesetzt in die Zeile drüber:	1	= 5⋅65 -9⋅(101 -1⋅ 65) = 5⋅65 -9⋅101 +9⋅ 65) = -9⋅101 +14⋅ 65 (=1)

Es gilt also: ggt(101,65)=1 = -9⋅101 +14⋅65

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

1 +9⋅101 = +14⋅65

Es gilt also: 14⋅65 = 9⋅101 +1

Somit 14⋅65 = 1 mod 101

14 ist also das Inverse von 65 mod 101