Um längere Rechnungen zu vermeiden, rechnen wir:

(11998 + 8004) mod 4 ≡ (11998 mod 4 + 8004 mod 4) mod 4.

11998 mod 4 ≡ 2 mod 4 kann man relativ leicht bestimmen, weil ja 11998 = 11000+998 = 4 ⋅ 2750 +998.

8004 mod 4 ≡ 0 mod 4 kann man relativ leicht bestimmen, weil ja 8004 = 8000+4 = 4 ⋅ 2000 +4.

Somit gilt:

(11998 + 8004) mod 4 ≡ (2 + 0) mod 4 ≡ 2 mod 4.

Um längere Rechnungen zu vermeiden, rechnen wir:

(19 ⋅ 44) mod 3 ≡ (19 mod 3 ⋅ 44 mod 3) mod 3.

19 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 19 = 18 + 1 = 6 ⋅ 3 + 1 ist.

44 mod 3 ≡ 2 mod 3 kann man relativ leicht bestimmen, weil ja 44 = 42 + 2 = 14 ⋅ 3 + 2 ist.

Somit gilt:

(19 ⋅ 44) mod 3 ≡ (1 ⋅ 2) mod 3 ≡ 2 mod 3.

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

2: 858²=858¹⁺¹=858¹⋅858¹ ≡ 858⋅858=736164 ≡ 396 mod 929

4: 858⁴=858²⁺²=858²⋅858² ≡ 396⋅396=156816 ≡ 744 mod 929

8: 858⁸=858⁴⁺⁴=858⁴⋅858⁴ ≡ 744⋅744=553536 ≡ 781 mod 929

16: 858¹⁶=858⁸⁺⁸=858⁸⋅858⁸ ≡ 781⋅781=609961 ≡ 537 mod 929

32: 858³²=858¹⁶⁺¹⁶=858¹⁶⋅858¹⁶ ≡ 537⋅537=288369 ≡ 379 mod 929

64: 858⁶⁴=858³²⁺³²=858³²⋅858³² ≡ 379⋅379=143641 ≡ 575 mod 929

128: 858¹²⁸=858⁶⁴⁺⁶⁴=858⁶⁴⋅858⁶⁴ ≡ 575⋅575=330625 ≡ 830 mod 929

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

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

188 = 128+32+16+8+4

452¹⁸⁸

= 452^{128+32+16+8+4}

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

≡ 350 ⋅ 67 ⋅ 244 ⋅ 385 ⋅ 107 mod 461
≡ 23450 ⋅ 244 ⋅ 385 ⋅ 107 mod 461 ≡ 400 ⋅ 244 ⋅ 385 ⋅ 107 mod 461
≡ 97600 ⋅ 385 ⋅ 107 mod 461 ≡ 329 ⋅ 385 ⋅ 107 mod 461
≡ 126665 ⋅ 107 mod 461 ≡ 351 ⋅ 107 mod 461
≡ 37557 mod 461 ≡ 216 mod 461

Es gilt also: 452¹⁸⁸ ≡ 216 mod 461

Berechnung des größten gemeinsamen Teilers von 67 und 42

=>67	= 1⋅42 + 25
=>42	= 1⋅25 + 17
=>25	= 1⋅17 + 8
=>17	= 2⋅8 + 1
=>8	= 8⋅1 + 0

also gilt: ggt(67,42)=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= 17-2⋅8
8= 25-1⋅17	eingesetzt in die Zeile drüber:	1	= 1⋅17 -2⋅(25 -1⋅ 17) = 1⋅17 -2⋅25 +2⋅ 17) = -2⋅25 +3⋅ 17 (=1)
17= 42-1⋅25	eingesetzt in die Zeile drüber:	1	= -2⋅25 +3⋅(42 -1⋅ 25) = -2⋅25 +3⋅42 -3⋅ 25) = 3⋅42 -5⋅ 25 (=1)
25= 67-1⋅42	eingesetzt in die Zeile drüber:	1	= 3⋅42 -5⋅(67 -1⋅ 42) = 3⋅42 -5⋅67 +5⋅ 42) = -5⋅67 +8⋅ 42 (=1)

Es gilt also: ggt(67,42)=1 = -5⋅67 +8⋅42

oder wenn man -5⋅67 auf die linke Seite bringt:

1 +5⋅67 = +8⋅42

Es gilt also: 8⋅42 = 5⋅67 +1

Somit 8⋅42 = 1 mod 67

8 ist also das Inverse von 42 mod 67