Um längere Rechnungen zu vermeiden, rechnen wir:

(168 + 79) mod 8 ≡ (168 mod 8 + 79 mod 8) mod 8.

168 mod 8 ≡ 0 mod 8 kann man relativ leicht bestimmen, weil ja 168 = 160+8 = 8 ⋅ 20 +8.

79 mod 8 ≡ 7 mod 8 kann man relativ leicht bestimmen, weil ja 79 = 80-1 = 8 ⋅ 10 -1 = 8 ⋅ 10 - 8 + 7.

Somit gilt:

(168 + 79) mod 8 ≡ (0 + 7) mod 8 ≡ 7 mod 8.

Um längere Rechnungen zu vermeiden, rechnen wir:

(56 ⋅ 74) mod 11 ≡ (56 mod 11 ⋅ 74 mod 11) mod 11.

56 mod 11 ≡ 1 mod 11 kann man relativ leicht bestimmen, weil ja 56 = 55 + 1 = 5 ⋅ 11 + 1 ist.

74 mod 11 ≡ 8 mod 11 kann man relativ leicht bestimmen, weil ja 74 = 66 + 8 = 6 ⋅ 11 + 8 ist.

Somit gilt:

(56 ⋅ 74) mod 11 ≡ (1 ⋅ 8) mod 11 ≡ 8 mod 11.

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

2: 234²=234¹⁺¹=234¹⋅234¹ ≡ 234⋅234=54756 ≡ 137 mod 283

4: 234⁴=234²⁺²=234²⋅234² ≡ 137⋅137=18769 ≡ 91 mod 283

8: 234⁸=234⁴⁺⁴=234⁴⋅234⁴ ≡ 91⋅91=8281 ≡ 74 mod 283

16: 234¹⁶=234⁸⁺⁸=234⁸⋅234⁸ ≡ 74⋅74=5476 ≡ 99 mod 283

32: 234³²=234¹⁶⁺¹⁶=234¹⁶⋅234¹⁶ ≡ 99⋅99=9801 ≡ 179 mod 283

64: 234⁶⁴=234³²⁺³²=234³²⋅234³² ≡ 179⋅179=32041 ≡ 62 mod 283

128: 234¹²⁸=234⁶⁴⁺⁶⁴=234⁶⁴⋅234⁶⁴ ≡ 62⋅62=3844 ≡ 165 mod 283

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

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

253 = 128+64+32+16+8+4+1

164²⁵³

= 164^{128+64+32+16+8+4+1}

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

≡ 256 ⋅ 16 ⋅ 4 ⋅ 2 ⋅ 60 ⋅ 211 ⋅ 164 mod 257
≡ 4096 ⋅ 4 ⋅ 2 ⋅ 60 ⋅ 211 ⋅ 164 mod 257 ≡ 241 ⋅ 4 ⋅ 2 ⋅ 60 ⋅ 211 ⋅ 164 mod 257
≡ 964 ⋅ 2 ⋅ 60 ⋅ 211 ⋅ 164 mod 257 ≡ 193 ⋅ 2 ⋅ 60 ⋅ 211 ⋅ 164 mod 257
≡ 386 ⋅ 60 ⋅ 211 ⋅ 164 mod 257 ≡ 129 ⋅ 60 ⋅ 211 ⋅ 164 mod 257
≡ 7740 ⋅ 211 ⋅ 164 mod 257 ≡ 30 ⋅ 211 ⋅ 164 mod 257
≡ 6330 ⋅ 164 mod 257 ≡ 162 ⋅ 164 mod 257
≡ 26568 mod 257 ≡ 97 mod 257

Es gilt also: 164²⁵³ ≡ 97 mod 257

Berechnung des größten gemeinsamen Teilers von 79 und 70

=>79	= 1⋅70 + 9
=>70	= 7⋅9 + 7
=>9	= 1⋅7 + 2
=>7	= 3⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(79,70)=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= 7-3⋅2
2= 9-1⋅7	eingesetzt in die Zeile drüber:	1	= 1⋅7 -3⋅(9 -1⋅ 7) = 1⋅7 -3⋅9 +3⋅ 7) = -3⋅9 +4⋅ 7 (=1)
7= 70-7⋅9	eingesetzt in die Zeile drüber:	1	= -3⋅9 +4⋅(70 -7⋅ 9) = -3⋅9 +4⋅70 -28⋅ 9) = 4⋅70 -31⋅ 9 (=1)
9= 79-1⋅70	eingesetzt in die Zeile drüber:	1	= 4⋅70 -31⋅(79 -1⋅ 70) = 4⋅70 -31⋅79 +31⋅ 70) = -31⋅79 +35⋅ 70 (=1)

Es gilt also: ggt(79,70)=1 = -31⋅79 +35⋅70

oder wenn man -31⋅79 auf die linke Seite bringt:

1 +31⋅79 = +35⋅70

Es gilt also: 35⋅70 = 31⋅79 +1

Somit 35⋅70 = 1 mod 79

35 ist also das Inverse von 70 mod 79