Um längere Rechnungen zu vermeiden, rechnen wir:

(3997 + 4005) mod 8 ≡ (3997 mod 8 + 4005 mod 8) mod 8.

3997 mod 8 ≡ 5 mod 8 kann man relativ leicht bestimmen, weil ja 3997 = 4000-3 = 8 ⋅ 500 -3 = 8 ⋅ 500 - 8 + 5.

4005 mod 8 ≡ 5 mod 8 kann man relativ leicht bestimmen, weil ja 4005 = 4000+5 = 8 ⋅ 500 +5.

Somit gilt:

(3997 + 4005) mod 8 ≡ (5 + 5) mod 8 ≡ 10 mod 8 ≡ 2 mod 8.

Um längere Rechnungen zu vermeiden, rechnen wir:

(21 ⋅ 70) mod 8 ≡ (21 mod 8 ⋅ 70 mod 8) mod 8.

21 mod 8 ≡ 5 mod 8 kann man relativ leicht bestimmen, weil ja 21 = 16 + 5 = 2 ⋅ 8 + 5 ist.

70 mod 8 ≡ 6 mod 8 kann man relativ leicht bestimmen, weil ja 70 = 64 + 6 = 8 ⋅ 8 + 6 ist.

Somit gilt:

(21 ⋅ 70) mod 8 ≡ (5 ⋅ 6) mod 8 ≡ 30 mod 8 ≡ 6 mod 8.

Die 64 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: 93¹=93

2: 93²=93¹⁺¹=93¹⋅93¹ ≡ 93⋅93=8649 ≡ 252 mod 311

4: 93⁴=93²⁺²=93²⋅93² ≡ 252⋅252=63504 ≡ 60 mod 311

8: 93⁸=93⁴⁺⁴=93⁴⋅93⁴ ≡ 60⋅60=3600 ≡ 179 mod 311

16: 93¹⁶=93⁸⁺⁸=93⁸⋅93⁸ ≡ 179⋅179=32041 ≡ 8 mod 311

32: 93³²=93¹⁶⁺¹⁶=93¹⁶⋅93¹⁶ ≡ 8⋅8=64 ≡ 64 mod 311

64: 93⁶⁴=93³²⁺³²=93³²⋅93³² ≡ 64⋅64=4096 ≡ 53 mod 311

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

460¹⁹¹

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

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

≡ 120 ⋅ 237 ⋅ 553 ⋅ 370 ⋅ 919 ⋅ 794 ⋅ 460 mod 967
≡ 28440 ⋅ 553 ⋅ 370 ⋅ 919 ⋅ 794 ⋅ 460 mod 967 ≡ 397 ⋅ 553 ⋅ 370 ⋅ 919 ⋅ 794 ⋅ 460 mod 967
≡ 219541 ⋅ 370 ⋅ 919 ⋅ 794 ⋅ 460 mod 967 ≡ 32 ⋅ 370 ⋅ 919 ⋅ 794 ⋅ 460 mod 967
≡ 11840 ⋅ 919 ⋅ 794 ⋅ 460 mod 967 ≡ 236 ⋅ 919 ⋅ 794 ⋅ 460 mod 967
≡ 216884 ⋅ 794 ⋅ 460 mod 967 ≡ 276 ⋅ 794 ⋅ 460 mod 967
≡ 219144 ⋅ 460 mod 967 ≡ 602 ⋅ 460 mod 967
≡ 276920 mod 967 ≡ 358 mod 967

Es gilt also: 460¹⁹¹ ≡ 358 mod 967

Berechnung des größten gemeinsamen Teilers von 59 und 55

=>59	= 1⋅55 + 4
=>55	= 13⋅4 + 3
=>4	= 1⋅3 + 1
=>3	= 3⋅1 + 0

also gilt: ggt(59,55)=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= 4-1⋅3
3= 55-13⋅4	eingesetzt in die Zeile drüber:	1	= 1⋅4 -1⋅(55 -13⋅ 4) = 1⋅4 -1⋅55 +13⋅ 4) = -1⋅55 +14⋅ 4 (=1)
4= 59-1⋅55	eingesetzt in die Zeile drüber:	1	= -1⋅55 +14⋅(59 -1⋅ 55) = -1⋅55 +14⋅59 -14⋅ 55) = 14⋅59 -15⋅ 55 (=1)

Es gilt also: ggt(59,55)=1 = 14⋅59 -15⋅55

oder wenn man 14⋅59 auf die linke Seite bringt:

1 -14⋅59 = -15⋅55

-15⋅55 = -14⋅59 + 1 |+59⋅55

-15⋅55 + 59⋅55 = -14⋅59 + 59⋅55 + 1

(-15 + 59) ⋅ 55 = (-14 + 55) ⋅ 59 + 1

44⋅55 = 41⋅59 + 1

Es gilt also: 44⋅55 = 41⋅59 +1

Somit 44⋅55 = 1 mod 59

44 ist also das Inverse von 55 mod 59