Um längere Rechnungen zu vermeiden, rechnen wir:

(37 - 122) mod 4 ≡ (37 mod 4 - 122 mod 4) mod 4.

37 mod 4 ≡ 1 mod 4 kann man relativ leicht bestimmen, weil ja 37 = 40-3 = 4 ⋅ 10 -3 = 4 ⋅ 10 - 4 + 1.

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

Somit gilt:

(37 - 122) mod 4 ≡ (1 - 2) mod 4 ≡ -1 mod 4 ≡ 3 mod 4.

Um längere Rechnungen zu vermeiden, rechnen wir:

(85 ⋅ 62) mod 7 ≡ (85 mod 7 ⋅ 62 mod 7) mod 7.

85 mod 7 ≡ 1 mod 7 kann man relativ leicht bestimmen, weil ja 85 = 84 + 1 = 12 ⋅ 7 + 1 ist.

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

Somit gilt:

(85 ⋅ 62) mod 7 ≡ (1 ⋅ 6) mod 7 ≡ 6 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: 198¹=198

2: 198²=198¹⁺¹=198¹⋅198¹ ≡ 198⋅198=39204 ≡ 244 mod 487

4: 198⁴=198²⁺²=198²⋅198² ≡ 244⋅244=59536 ≡ 122 mod 487

8: 198⁸=198⁴⁺⁴=198⁴⋅198⁴ ≡ 122⋅122=14884 ≡ 274 mod 487

16: 198¹⁶=198⁸⁺⁸=198⁸⋅198⁸ ≡ 274⋅274=75076 ≡ 78 mod 487

32: 198³²=198¹⁶⁺¹⁶=198¹⁶⋅198¹⁶ ≡ 78⋅78=6084 ≡ 240 mod 487

64: 198⁶⁴=198³²⁺³²=198³²⋅198³² ≡ 240⋅240=57600 ≡ 134 mod 487

128: 198¹²⁸=198⁶⁴⁺⁶⁴=198⁶⁴⋅198⁶⁴ ≡ 134⋅134=17956 ≡ 424 mod 487

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

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

208 = 128+64+16

252²⁰⁸

= 252^128+64+16

= 252¹²⁸⋅252⁶⁴⋅252¹⁶

≡ 346 ⋅ 644 ⋅ 394 mod 727
≡ 222824 ⋅ 394 mod 727 ≡ 362 ⋅ 394 mod 727
≡ 142628 mod 727 ≡ 136 mod 727

Es gilt also: 252²⁰⁸ ≡ 136 mod 727

Berechnung des größten gemeinsamen Teilers von 73 und 54

=>73	= 1⋅54 + 19
=>54	= 2⋅19 + 16
=>19	= 1⋅16 + 3
=>16	= 5⋅3 + 1
=>3	= 3⋅1 + 0

also gilt: ggt(73,54)=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= 16-5⋅3
3= 19-1⋅16	eingesetzt in die Zeile drüber:	1	= 1⋅16 -5⋅(19 -1⋅ 16) = 1⋅16 -5⋅19 +5⋅ 16) = -5⋅19 +6⋅ 16 (=1)
16= 54-2⋅19	eingesetzt in die Zeile drüber:	1	= -5⋅19 +6⋅(54 -2⋅ 19) = -5⋅19 +6⋅54 -12⋅ 19) = 6⋅54 -17⋅ 19 (=1)
19= 73-1⋅54	eingesetzt in die Zeile drüber:	1	= 6⋅54 -17⋅(73 -1⋅ 54) = 6⋅54 -17⋅73 +17⋅ 54) = -17⋅73 +23⋅ 54 (=1)

Es gilt also: ggt(73,54)=1 = -17⋅73 +23⋅54

oder wenn man -17⋅73 auf die linke Seite bringt:

1 +17⋅73 = +23⋅54

Es gilt also: 23⋅54 = 17⋅73 +1

Somit 23⋅54 = 1 mod 73

23 ist also das Inverse von 54 mod 73