Um längere Rechnungen zu vermeiden, rechnen wir:

(156 + 31993) mod 8 ≡ (156 mod 8 + 31993 mod 8) mod 8.

156 mod 8 ≡ 4 mod 8 kann man relativ leicht bestimmen, weil ja 156 = 160-4 = 8 ⋅ 20 -4 = 8 ⋅ 20 - 8 + 4.

31993 mod 8 ≡ 1 mod 8 kann man relativ leicht bestimmen, weil ja 31993 = 31000+993 = 8 ⋅ 3875 +993.

Somit gilt:

(156 + 31993) mod 8 ≡ (4 + 1) mod 8 ≡ 5 mod 8.

Um längere Rechnungen zu vermeiden, rechnen wir:

(63 ⋅ 43) mod 7 ≡ (63 mod 7 ⋅ 43 mod 7) mod 7.

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

43 mod 7 ≡ 1 mod 7 kann man relativ leicht bestimmen, weil ja 43 = 42 + 1 = 6 ⋅ 7 + 1 ist.

Somit gilt:

(63 ⋅ 43) mod 7 ≡ (0 ⋅ 1) 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: 126¹=126

2: 126²=126¹⁺¹=126¹⋅126¹ ≡ 126⋅126=15876 ≡ 219 mod 307

4: 126⁴=126²⁺²=126²⋅126² ≡ 219⋅219=47961 ≡ 69 mod 307

8: 126⁸=126⁴⁺⁴=126⁴⋅126⁴ ≡ 69⋅69=4761 ≡ 156 mod 307

16: 126¹⁶=126⁸⁺⁸=126⁸⋅126⁸ ≡ 156⋅156=24336 ≡ 83 mod 307

32: 126³²=126¹⁶⁺¹⁶=126¹⁶⋅126¹⁶ ≡ 83⋅83=6889 ≡ 135 mod 307

64: 126⁶⁴=126³²⁺³²=126³²⋅126³² ≡ 135⋅135=18225 ≡ 112 mod 307

128: 126¹²⁸=126⁶⁴⁺⁶⁴=126⁶⁴⋅126⁶⁴ ≡ 112⋅112=12544 ≡ 264 mod 307

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

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

229 = 128+64+32+4+1

187²²⁹

= 187^{128+64+32+4+1}

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

≡ 256 ⋅ 337 ⋅ 185 ⋅ 131 ⋅ 187 mod 353
≡ 86272 ⋅ 185 ⋅ 131 ⋅ 187 mod 353 ≡ 140 ⋅ 185 ⋅ 131 ⋅ 187 mod 353
≡ 25900 ⋅ 131 ⋅ 187 mod 353 ≡ 131 ⋅ 131 ⋅ 187 mod 353
≡ 17161 ⋅ 187 mod 353 ≡ 217 ⋅ 187 mod 353
≡ 40579 mod 353 ≡ 337 mod 353

Es gilt also: 187²²⁹ ≡ 337 mod 353

Berechnung des größten gemeinsamen Teilers von 61 und 35

=>61	= 1⋅35 + 26
=>35	= 1⋅26 + 9
=>26	= 2⋅9 + 8
=>9	= 1⋅8 + 1
=>8	= 8⋅1 + 0

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

Es gilt also: ggt(61,35)=1 = -4⋅61 +7⋅35

oder wenn man -4⋅61 auf die linke Seite bringt:

1 +4⋅61 = +7⋅35

Es gilt also: 7⋅35 = 4⋅61 +1

Somit 7⋅35 = 1 mod 61

7 ist also das Inverse von 35 mod 61