Um längere Rechnungen zu vermeiden, rechnen wir:

(3592 - 9003) mod 9 ≡ (3592 mod 9 - 9003 mod 9) mod 9.

3592 mod 9 ≡ 1 mod 9 kann man relativ leicht bestimmen, weil ja 3592 = 3600-8 = 9 ⋅ 400 -8 = 9 ⋅ 400 - 9 + 1.

9003 mod 9 ≡ 3 mod 9 kann man relativ leicht bestimmen, weil ja 9003 = 9000+3 = 9 ⋅ 1000 +3.

Somit gilt:

(3592 - 9003) mod 9 ≡ (1 - 3) mod 9 ≡ -2 mod 9 ≡ 7 mod 9.

Um längere Rechnungen zu vermeiden, rechnen wir:

(79 ⋅ 62) mod 9 ≡ (79 mod 9 ⋅ 62 mod 9) mod 9.

79 mod 9 ≡ 7 mod 9 kann man relativ leicht bestimmen, weil ja 79 = 72 + 7 = 8 ⋅ 9 + 7 ist.

62 mod 9 ≡ 8 mod 9 kann man relativ leicht bestimmen, weil ja 62 = 54 + 8 = 6 ⋅ 9 + 8 ist.

Somit gilt:

(79 ⋅ 62) mod 9 ≡ (7 ⋅ 8) mod 9 ≡ 56 mod 9 ≡ 2 mod 9.

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

2: 737²=737¹⁺¹=737¹⋅737¹ ≡ 737⋅737=543169 ≡ 4 mod 739

4: 737⁴=737²⁺²=737²⋅737² ≡ 4⋅4=16 ≡ 16 mod 739

8: 737⁸=737⁴⁺⁴=737⁴⋅737⁴ ≡ 16⋅16=256 ≡ 256 mod 739

16: 737¹⁶=737⁸⁺⁸=737⁸⋅737⁸ ≡ 256⋅256=65536 ≡ 504 mod 739

32: 737³²=737¹⁶⁺¹⁶=737¹⁶⋅737¹⁶ ≡ 504⋅504=254016 ≡ 539 mod 739

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

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

246 = 128+64+32+16+4+2

321²⁴⁶

= 321^{128+64+32+16+4+2}

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

≡ 285 ⋅ 431 ⋅ 405 ⋅ 228 ⋅ 143 ⋅ 404 mod 521
≡ 122835 ⋅ 405 ⋅ 228 ⋅ 143 ⋅ 404 mod 521 ≡ 400 ⋅ 405 ⋅ 228 ⋅ 143 ⋅ 404 mod 521
≡ 162000 ⋅ 228 ⋅ 143 ⋅ 404 mod 521 ≡ 490 ⋅ 228 ⋅ 143 ⋅ 404 mod 521
≡ 111720 ⋅ 143 ⋅ 404 mod 521 ≡ 226 ⋅ 143 ⋅ 404 mod 521
≡ 32318 ⋅ 404 mod 521 ≡ 16 ⋅ 404 mod 521
≡ 6464 mod 521 ≡ 212 mod 521

Es gilt also: 321²⁴⁶ ≡ 212 mod 521

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

=>61	= 1⋅42 + 19
=>42	= 2⋅19 + 4
=>19	= 4⋅4 + 3
=>4	= 1⋅3 + 1
=>3	= 3⋅1 + 0

also gilt: ggt(61,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= 4-1⋅3
3= 19-4⋅4	eingesetzt in die Zeile drüber:	1	= 1⋅4 -1⋅(19 -4⋅ 4) = 1⋅4 -1⋅19 +4⋅ 4) = -1⋅19 +5⋅ 4 (=1)
4= 42-2⋅19	eingesetzt in die Zeile drüber:	1	= -1⋅19 +5⋅(42 -2⋅ 19) = -1⋅19 +5⋅42 -10⋅ 19) = 5⋅42 -11⋅ 19 (=1)
19= 61-1⋅42	eingesetzt in die Zeile drüber:	1	= 5⋅42 -11⋅(61 -1⋅ 42) = 5⋅42 -11⋅61 +11⋅ 42) = -11⋅61 +16⋅ 42 (=1)

Es gilt also: ggt(61,42)=1 = -11⋅61 +16⋅42

oder wenn man -11⋅61 auf die linke Seite bringt:

1 +11⋅61 = +16⋅42

Es gilt also: 16⋅42 = 11⋅61 +1

Somit 16⋅42 = 1 mod 61

16 ist also das Inverse von 42 mod 61