Um längere Rechnungen zu vermeiden, rechnen wir:

(1797 - 23995) mod 6 ≡ (1797 mod 6 - 23995 mod 6) mod 6.

1797 mod 6 ≡ 3 mod 6 kann man relativ leicht bestimmen, weil ja 1797 = 1800-3 = 6 ⋅ 300 -3 = 6 ⋅ 300 - 6 + 3.

23995 mod 6 ≡ 1 mod 6 kann man relativ leicht bestimmen, weil ja 23995 = 24000-5 = 6 ⋅ 4000 -5 = 6 ⋅ 4000 - 6 + 1.

Somit gilt:

(1797 - 23995) mod 6 ≡ (3 - 1) mod 6 ≡ 2 mod 6.

Um längere Rechnungen zu vermeiden, rechnen wir:

(58 ⋅ 51) mod 10 ≡ (58 mod 10 ⋅ 51 mod 10) mod 10.

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

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

Somit gilt:

(58 ⋅ 51) mod 10 ≡ (8 ⋅ 1) mod 10 ≡ 8 mod 10.

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

2: 464²=464¹⁺¹=464¹⋅464¹ ≡ 464⋅464=215296 ≡ 138 mod 601

4: 464⁴=464²⁺²=464²⋅464² ≡ 138⋅138=19044 ≡ 413 mod 601

8: 464⁸=464⁴⁺⁴=464⁴⋅464⁴ ≡ 413⋅413=170569 ≡ 486 mod 601

16: 464¹⁶=464⁸⁺⁸=464⁸⋅464⁸ ≡ 486⋅486=236196 ≡ 3 mod 601

32: 464³²=464¹⁶⁺¹⁶=464¹⁶⋅464¹⁶ ≡ 3⋅3=9 ≡ 9 mod 601

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

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

220 = 128+64+16+8+4

689²²⁰

= 689^{128+64+16+8+4}

= 689¹²⁸⋅689⁶⁴⋅689¹⁶⋅689⁸⋅689⁴

≡ 332 ⋅ 877 ⋅ 196 ⋅ 927 ⋅ 888 mod 941
≡ 291164 ⋅ 196 ⋅ 927 ⋅ 888 mod 941 ≡ 395 ⋅ 196 ⋅ 927 ⋅ 888 mod 941
≡ 77420 ⋅ 927 ⋅ 888 mod 941 ≡ 258 ⋅ 927 ⋅ 888 mod 941
≡ 239166 ⋅ 888 mod 941 ≡ 152 ⋅ 888 mod 941
≡ 134976 mod 941 ≡ 413 mod 941

Es gilt also: 689²²⁰ ≡ 413 mod 941

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

=>59	= 1⋅47 + 12
=>47	= 3⋅12 + 11
=>12	= 1⋅11 + 1
=>11	= 11⋅1 + 0

also gilt: ggt(59,47)=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= 12-1⋅11
11= 47-3⋅12	eingesetzt in die Zeile drüber:	1	= 1⋅12 -1⋅(47 -3⋅ 12) = 1⋅12 -1⋅47 +3⋅ 12) = -1⋅47 +4⋅ 12 (=1)
12= 59-1⋅47	eingesetzt in die Zeile drüber:	1	= -1⋅47 +4⋅(59 -1⋅ 47) = -1⋅47 +4⋅59 -4⋅ 47) = 4⋅59 -5⋅ 47 (=1)

Es gilt also: ggt(59,47)=1 = 4⋅59 -5⋅47

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

1 -4⋅59 = -5⋅47

-5⋅47 = -4⋅59 + 1 |+59⋅47

-5⋅47 + 59⋅47 = -4⋅59 + 59⋅47 + 1

(-5 + 59) ⋅ 47 = (-4 + 47) ⋅ 59 + 1

54⋅47 = 43⋅59 + 1

Es gilt also: 54⋅47 = 43⋅59 +1

Somit 54⋅47 = 1 mod 59

54 ist also das Inverse von 47 mod 59