Um längere Rechnungen zu vermeiden, rechnen wir:

(2001 + 20001) mod 4 ≡ (2001 mod 4 + 20001 mod 4) mod 4.

2001 mod 4 ≡ 1 mod 4 kann man relativ leicht bestimmen, weil ja 2001 = 2000+1 = 4 ⋅ 500 +1.

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

Somit gilt:

(2001 + 20001) mod 4 ≡ (1 + 1) mod 4 ≡ 2 mod 4.

Um längere Rechnungen zu vermeiden, rechnen wir:

(51 ⋅ 36) mod 5 ≡ (51 mod 5 ⋅ 36 mod 5) mod 5.

51 mod 5 ≡ 1 mod 5 kann man relativ leicht bestimmen, weil ja 51 = 50 + 1 = 10 ⋅ 5 + 1 ist.

36 mod 5 ≡ 1 mod 5 kann man relativ leicht bestimmen, weil ja 36 = 35 + 1 = 7 ⋅ 5 + 1 ist.

Somit gilt:

(51 ⋅ 36) mod 5 ≡ (1 ⋅ 1) mod 5 ≡ 1 mod 5.

Die 32 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: 452¹=452

2: 452²=452¹⁺¹=452¹⋅452¹ ≡ 452⋅452=204304 ≡ 527 mod 677

4: 452⁴=452²⁺²=452²⋅452² ≡ 527⋅527=277729 ≡ 159 mod 677

8: 452⁸=452⁴⁺⁴=452⁴⋅452⁴ ≡ 159⋅159=25281 ≡ 232 mod 677

16: 452¹⁶=452⁸⁺⁸=452⁸⋅452⁸ ≡ 232⋅232=53824 ≡ 341 mod 677

32: 452³²=452¹⁶⁺¹⁶=452¹⁶⋅452¹⁶ ≡ 341⋅341=116281 ≡ 514 mod 677

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

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

118 = 64+32+16+4+2

266¹¹⁸

= 266^64+32+16+4+2

= 266⁶⁴⋅266³²⋅266¹⁶⋅266⁴⋅266²

≡ 140 ⋅ 144 ⋅ 259 ⋅ 83 ⋅ 25 mod 271
≡ 20160 ⋅ 259 ⋅ 83 ⋅ 25 mod 271 ≡ 106 ⋅ 259 ⋅ 83 ⋅ 25 mod 271
≡ 27454 ⋅ 83 ⋅ 25 mod 271 ≡ 83 ⋅ 83 ⋅ 25 mod 271
≡ 6889 ⋅ 25 mod 271 ≡ 114 ⋅ 25 mod 271
≡ 2850 mod 271 ≡ 140 mod 271

Es gilt also: 266¹¹⁸ ≡ 140 mod 271

Berechnung des größten gemeinsamen Teilers von 83 und 43

=>83	= 1⋅43 + 40
=>43	= 1⋅40 + 3
=>40	= 13⋅3 + 1
=>3	= 3⋅1 + 0

also gilt: ggt(83,43)=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= 40-13⋅3
3= 43-1⋅40	eingesetzt in die Zeile drüber:	1	= 1⋅40 -13⋅(43 -1⋅ 40) = 1⋅40 -13⋅43 +13⋅ 40) = -13⋅43 +14⋅ 40 (=1)
40= 83-1⋅43	eingesetzt in die Zeile drüber:	1	= -13⋅43 +14⋅(83 -1⋅ 43) = -13⋅43 +14⋅83 -14⋅ 43) = 14⋅83 -27⋅ 43 (=1)

Es gilt also: ggt(83,43)=1 = 14⋅83 -27⋅43

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

1 -14⋅83 = -27⋅43

-27⋅43 = -14⋅83 + 1 |+83⋅43

-27⋅43 + 83⋅43 = -14⋅83 + 83⋅43 + 1

(-27 + 83) ⋅ 43 = (-14 + 43) ⋅ 83 + 1

56⋅43 = 29⋅83 + 1

Es gilt also: 56⋅43 = 29⋅83 +1

Somit 56⋅43 = 1 mod 83

56 ist also das Inverse von 43 mod 83