Um längere Rechnungen zu vermeiden, rechnen wir:

(8005 + 313) mod 8 ≡ (8005 mod 8 + 313 mod 8) mod 8.

8005 mod 8 ≡ 5 mod 8 kann man relativ leicht bestimmen, weil ja 8005 = 8000+5 = 8 ⋅ 1000 +5.

313 mod 8 ≡ 1 mod 8 kann man relativ leicht bestimmen, weil ja 313 = 320-7 = 8 ⋅ 40 -7 = 8 ⋅ 40 - 8 + 1.

Somit gilt:

(8005 + 313) mod 8 ≡ (5 + 1) mod 8 ≡ 6 mod 8.

Um längere Rechnungen zu vermeiden, rechnen wir:

(69 ⋅ 29) mod 7 ≡ (69 mod 7 ⋅ 29 mod 7) mod 7.

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

29 mod 7 ≡ 1 mod 7 kann man relativ leicht bestimmen, weil ja 29 = 28 + 1 = 4 ⋅ 7 + 1 ist.

Somit gilt:

(69 ⋅ 29) mod 7 ≡ (6 ⋅ 1) mod 7 ≡ 6 mod 7.

Die 16 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: 273¹=273

2: 273²=273¹⁺¹=273¹⋅273¹ ≡ 273⋅273=74529 ≡ 559 mod 569

4: 273⁴=273²⁺²=273²⋅273² ≡ 559⋅559=312481 ≡ 100 mod 569

8: 273⁸=273⁴⁺⁴=273⁴⋅273⁴ ≡ 100⋅100=10000 ≡ 327 mod 569

16: 273¹⁶=273⁸⁺⁸=273⁸⋅273⁸ ≡ 327⋅327=106929 ≡ 526 mod 569

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

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

191 = 128+32+16+8+4+2+1

83¹⁹¹

= 83^{128+32+16+8+4+2+1}

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

≡ 256 ⋅ 253 ⋅ 32 ⋅ 17 ⋅ 187 ⋅ 207 ⋅ 83 mod 257
≡ 64768 ⋅ 32 ⋅ 17 ⋅ 187 ⋅ 207 ⋅ 83 mod 257 ≡ 4 ⋅ 32 ⋅ 17 ⋅ 187 ⋅ 207 ⋅ 83 mod 257
≡ 128 ⋅ 17 ⋅ 187 ⋅ 207 ⋅ 83 mod 257
≡ 2176 ⋅ 187 ⋅ 207 ⋅ 83 mod 257 ≡ 120 ⋅ 187 ⋅ 207 ⋅ 83 mod 257
≡ 22440 ⋅ 207 ⋅ 83 mod 257 ≡ 81 ⋅ 207 ⋅ 83 mod 257
≡ 16767 ⋅ 83 mod 257 ≡ 62 ⋅ 83 mod 257
≡ 5146 mod 257 ≡ 6 mod 257

Es gilt also: 83¹⁹¹ ≡ 6 mod 257

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

=>79	= 2⋅27 + 25
=>27	= 1⋅25 + 2
=>25	= 12⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(79,27)=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= 25-12⋅2
2= 27-1⋅25	eingesetzt in die Zeile drüber:	1	= 1⋅25 -12⋅(27 -1⋅ 25) = 1⋅25 -12⋅27 +12⋅ 25) = -12⋅27 +13⋅ 25 (=1)
25= 79-2⋅27	eingesetzt in die Zeile drüber:	1	= -12⋅27 +13⋅(79 -2⋅ 27) = -12⋅27 +13⋅79 -26⋅ 27) = 13⋅79 -38⋅ 27 (=1)

Es gilt also: ggt(79,27)=1 = 13⋅79 -38⋅27

oder wenn man 13⋅79 auf die linke Seite bringt:

1 -13⋅79 = -38⋅27

-38⋅27 = -13⋅79 + 1 |+79⋅27

-38⋅27 + 79⋅27 = -13⋅79 + 79⋅27 + 1

(-38 + 79) ⋅ 27 = (-13 + 27) ⋅ 79 + 1

41⋅27 = 14⋅79 + 1

Es gilt also: 41⋅27 = 14⋅79 +1

Somit 41⋅27 = 1 mod 79

41 ist also das Inverse von 27 mod 79