Um längere Rechnungen zu vermeiden, rechnen wir:

(199 + 20004) mod 4 ≡ (199 mod 4 + 20004 mod 4) mod 4.

199 mod 4 ≡ 3 mod 4 kann man relativ leicht bestimmen, weil ja 199 = 200-1 = 4 ⋅ 50 -1 = 4 ⋅ 50 - 4 + 3.

20004 mod 4 ≡ 0 mod 4 kann man relativ leicht bestimmen, weil ja 20004 = 20000+4 = 4 ⋅ 5000 +4.

Somit gilt:

(199 + 20004) mod 4 ≡ (3 + 0) mod 4 ≡ 3 mod 4.

Um längere Rechnungen zu vermeiden, rechnen wir:

(30 ⋅ 40) mod 9 ≡ (30 mod 9 ⋅ 40 mod 9) mod 9.

30 mod 9 ≡ 3 mod 9 kann man relativ leicht bestimmen, weil ja 30 = 27 + 3 = 3 ⋅ 9 + 3 ist.

40 mod 9 ≡ 4 mod 9 kann man relativ leicht bestimmen, weil ja 40 = 36 + 4 = 4 ⋅ 9 + 4 ist.

Somit gilt:

(30 ⋅ 40) mod 9 ≡ (3 ⋅ 4) mod 9 ≡ 12 mod 9 ≡ 3 mod 9.

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 ≡ 237 mod 401

4: 126⁴=126²⁺²=126²⋅126² ≡ 237⋅237=56169 ≡ 29 mod 401

8: 126⁸=126⁴⁺⁴=126⁴⋅126⁴ ≡ 29⋅29=841 ≡ 39 mod 401

16: 126¹⁶=126⁸⁺⁸=126⁸⋅126⁸ ≡ 39⋅39=1521 ≡ 318 mod 401

32: 126³²=126¹⁶⁺¹⁶=126¹⁶⋅126¹⁶ ≡ 318⋅318=101124 ≡ 72 mod 401

64: 126⁶⁴=126³²⁺³²=126³²⋅126³² ≡ 72⋅72=5184 ≡ 372 mod 401

128: 126¹²⁸=126⁶⁴⁺⁶⁴=126⁶⁴⋅126⁶⁴ ≡ 372⋅372=138384 ≡ 39 mod 401

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

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

251 = 128+64+32+16+8+2+1

418²⁵¹

= 418^{128+64+32+16+8+2+1}

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

≡ 350 ⋅ 559 ⋅ 418 ⋅ 311 ⋅ 243 ⋅ 559 ⋅ 418 mod 683
≡ 195650 ⋅ 418 ⋅ 311 ⋅ 243 ⋅ 559 ⋅ 418 mod 683 ≡ 312 ⋅ 418 ⋅ 311 ⋅ 243 ⋅ 559 ⋅ 418 mod 683
≡ 130416 ⋅ 311 ⋅ 243 ⋅ 559 ⋅ 418 mod 683 ≡ 646 ⋅ 311 ⋅ 243 ⋅ 559 ⋅ 418 mod 683
≡ 200906 ⋅ 243 ⋅ 559 ⋅ 418 mod 683 ≡ 104 ⋅ 243 ⋅ 559 ⋅ 418 mod 683
≡ 25272 ⋅ 559 ⋅ 418 mod 683 ≡ 1 ⋅ 559 ⋅ 418 mod 683
≡ 559 ⋅ 418 mod 683
≡ 233662 mod 683 ≡ 76 mod 683

Es gilt also: 418²⁵¹ ≡ 76 mod 683

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

=>59	= 1⋅38 + 21
=>38	= 1⋅21 + 17
=>21	= 1⋅17 + 4
=>17	= 4⋅4 + 1
=>4	= 4⋅1 + 0

also gilt: ggt(59,38)=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-4⋅4
4= 21-1⋅17	eingesetzt in die Zeile drüber:	1	= 1⋅17 -4⋅(21 -1⋅ 17) = 1⋅17 -4⋅21 +4⋅ 17) = -4⋅21 +5⋅ 17 (=1)
17= 38-1⋅21	eingesetzt in die Zeile drüber:	1	= -4⋅21 +5⋅(38 -1⋅ 21) = -4⋅21 +5⋅38 -5⋅ 21) = 5⋅38 -9⋅ 21 (=1)
21= 59-1⋅38	eingesetzt in die Zeile drüber:	1	= 5⋅38 -9⋅(59 -1⋅ 38) = 5⋅38 -9⋅59 +9⋅ 38) = -9⋅59 +14⋅ 38 (=1)

Es gilt also: ggt(59,38)=1 = -9⋅59 +14⋅38

oder wenn man -9⋅59 auf die linke Seite bringt:

1 +9⋅59 = +14⋅38

Es gilt also: 14⋅38 = 9⋅59 +1

Somit 14⋅38 = 1 mod 59

14 ist also das Inverse von 38 mod 59