Um längere Rechnungen zu vermeiden, rechnen wir:

(295 + 11994) mod 6 ≡ (295 mod 6 + 11994 mod 6) mod 6.

295 mod 6 ≡ 1 mod 6 kann man relativ leicht bestimmen, weil ja 295 = 300-5 = 6 ⋅ 50 -5 = 6 ⋅ 50 - 6 + 1.

11994 mod 6 ≡ 0 mod 6 kann man relativ leicht bestimmen, weil ja 11994 = 12000-6 = 6 ⋅ 2000 -6 = 6 ⋅ 2000 - 6 + 0.

Somit gilt:

(295 + 11994) mod 6 ≡ (1 + 0) mod 6 ≡ 1 mod 6.

Um längere Rechnungen zu vermeiden, rechnen wir:

(45 ⋅ 75) mod 4 ≡ (45 mod 4 ⋅ 75 mod 4) mod 4.

45 mod 4 ≡ 1 mod 4 kann man relativ leicht bestimmen, weil ja 45 = 44 + 1 = 11 ⋅ 4 + 1 ist.

75 mod 4 ≡ 3 mod 4 kann man relativ leicht bestimmen, weil ja 75 = 72 + 3 = 18 ⋅ 4 + 3 ist.

Somit gilt:

(45 ⋅ 75) mod 4 ≡ (1 ⋅ 3) mod 4 ≡ 3 mod 4.

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

2: 184²=184¹⁺¹=184¹⋅184¹ ≡ 184⋅184=33856 ≡ 96 mod 211

4: 184⁴=184²⁺²=184²⋅184² ≡ 96⋅96=9216 ≡ 143 mod 211

8: 184⁸=184⁴⁺⁴=184⁴⋅184⁴ ≡ 143⋅143=20449 ≡ 193 mod 211

16: 184¹⁶=184⁸⁺⁸=184⁸⋅184⁸ ≡ 193⋅193=37249 ≡ 113 mod 211

32: 184³²=184¹⁶⁺¹⁶=184¹⁶⋅184¹⁶ ≡ 113⋅113=12769 ≡ 109 mod 211

64: 184⁶⁴=184³²⁺³²=184³²⋅184³² ≡ 109⋅109=11881 ≡ 65 mod 211

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

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

242 = 128+64+32+16+2

391²⁴²

= 391^{128+64+32+16+2}

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

≡ 33 ⋅ 361 ⋅ 460 ⋅ 192 ⋅ 80 mod 479
≡ 11913 ⋅ 460 ⋅ 192 ⋅ 80 mod 479 ≡ 417 ⋅ 460 ⋅ 192 ⋅ 80 mod 479
≡ 191820 ⋅ 192 ⋅ 80 mod 479 ≡ 220 ⋅ 192 ⋅ 80 mod 479
≡ 42240 ⋅ 80 mod 479 ≡ 88 ⋅ 80 mod 479
≡ 7040 mod 479 ≡ 334 mod 479

Es gilt also: 391²⁴² ≡ 334 mod 479

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

=>79	= 1⋅64 + 15
=>64	= 4⋅15 + 4
=>15	= 3⋅4 + 3
=>4	= 1⋅3 + 1
=>3	= 3⋅1 + 0

also gilt: ggt(79,64)=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= 15-3⋅4	eingesetzt in die Zeile drüber:	1	= 1⋅4 -1⋅(15 -3⋅ 4) = 1⋅4 -1⋅15 +3⋅ 4) = -1⋅15 +4⋅ 4 (=1)
4= 64-4⋅15	eingesetzt in die Zeile drüber:	1	= -1⋅15 +4⋅(64 -4⋅ 15) = -1⋅15 +4⋅64 -16⋅ 15) = 4⋅64 -17⋅ 15 (=1)
15= 79-1⋅64	eingesetzt in die Zeile drüber:	1	= 4⋅64 -17⋅(79 -1⋅ 64) = 4⋅64 -17⋅79 +17⋅ 64) = -17⋅79 +21⋅ 64 (=1)

Es gilt also: ggt(79,64)=1 = -17⋅79 +21⋅64

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

1 +17⋅79 = +21⋅64

Es gilt also: 21⋅64 = 17⋅79 +1

Somit 21⋅64 = 1 mod 79

21 ist also das Inverse von 64 mod 79