Um längere Rechnungen zu vermeiden, rechnen wir:

(1198 + 118) mod 4 ≡ (1198 mod 4 + 118 mod 4) mod 4.

1198 mod 4 ≡ 2 mod 4 kann man relativ leicht bestimmen, weil ja 1198 = 1100+98 = 4 ⋅ 275 +98.

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

Somit gilt:

(1198 + 118) mod 4 ≡ (2 + 2) mod 4 ≡ 4 mod 4 ≡ 0 mod 4.

Um längere Rechnungen zu vermeiden, rechnen wir:

(17 ⋅ 31) mod 3 ≡ (17 mod 3 ⋅ 31 mod 3) mod 3.

17 mod 3 ≡ 2 mod 3 kann man relativ leicht bestimmen, weil ja 17 = 15 + 2 = 5 ⋅ 3 + 2 ist.

31 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 31 = 30 + 1 = 10 ⋅ 3 + 1 ist.

Somit gilt:

(17 ⋅ 31) mod 3 ≡ (2 ⋅ 1) mod 3 ≡ 2 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: 931¹=931

2: 931²=931¹⁺¹=931¹⋅931¹ ≡ 931⋅931=866761 ≡ 368 mod 997

4: 931⁴=931²⁺²=931²⋅931² ≡ 368⋅368=135424 ≡ 829 mod 997

8: 931⁸=931⁴⁺⁴=931⁴⋅931⁴ ≡ 829⋅829=687241 ≡ 308 mod 997

16: 931¹⁶=931⁸⁺⁸=931⁸⋅931⁸ ≡ 308⋅308=94864 ≡ 149 mod 997

32: 931³²=931¹⁶⁺¹⁶=931¹⁶⋅931¹⁶ ≡ 149⋅149=22201 ≡ 267 mod 997

64: 931⁶⁴=931³²⁺³²=931³²⋅931³² ≡ 267⋅267=71289 ≡ 502 mod 997

128: 931¹²⁸=931⁶⁴⁺⁶⁴=931⁶⁴⋅931⁶⁴ ≡ 502⋅502=252004 ≡ 760 mod 997

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

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

141 = 128+8+4+1

165¹⁴¹

= 165^128+8+4+1

= 165¹²⁸⋅165⁸⋅165⁴⋅165¹

≡ 90 ⋅ 3 ⋅ 147 ⋅ 165 mod 277
≡ 270 ⋅ 147 ⋅ 165 mod 277
≡ 39690 ⋅ 165 mod 277 ≡ 79 ⋅ 165 mod 277
≡ 13035 mod 277 ≡ 16 mod 277

Es gilt also: 165¹⁴¹ ≡ 16 mod 277

Berechnung des größten gemeinsamen Teilers von 71 und 25

=>71	= 2⋅25 + 21
=>25	= 1⋅21 + 4
=>21	= 5⋅4 + 1
=>4	= 4⋅1 + 0

also gilt: ggt(71,25)=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= 21-5⋅4
4= 25-1⋅21	eingesetzt in die Zeile drüber:	1	= 1⋅21 -5⋅(25 -1⋅ 21) = 1⋅21 -5⋅25 +5⋅ 21) = -5⋅25 +6⋅ 21 (=1)
21= 71-2⋅25	eingesetzt in die Zeile drüber:	1	= -5⋅25 +6⋅(71 -2⋅ 25) = -5⋅25 +6⋅71 -12⋅ 25) = 6⋅71 -17⋅ 25 (=1)

Es gilt also: ggt(71,25)=1 = 6⋅71 -17⋅25

oder wenn man 6⋅71 auf die linke Seite bringt:

1 -6⋅71 = -17⋅25

-17⋅25 = -6⋅71 + 1 |+71⋅25

-17⋅25 + 71⋅25 = -6⋅71 + 71⋅25 + 1

(-17 + 71) ⋅ 25 = (-6 + 25) ⋅ 71 + 1

54⋅25 = 19⋅71 + 1

Es gilt also: 54⋅25 = 19⋅71 +1

Somit 54⋅25 = 1 mod 71

54 ist also das Inverse von 25 mod 71