Um längere Rechnungen zu vermeiden, rechnen wir:

(3604 + 3605) mod 9 ≡ (3604 mod 9 + 3605 mod 9) mod 9.

3604 mod 9 ≡ 4 mod 9 kann man relativ leicht bestimmen, weil ja 3604 = 3600+4 = 9 ⋅ 400 +4.

3605 mod 9 ≡ 5 mod 9 kann man relativ leicht bestimmen, weil ja 3605 = 3600+5 = 9 ⋅ 400 +5.

Somit gilt:

(3604 + 3605) mod 9 ≡ (4 + 5) mod 9 ≡ 9 mod 9 ≡ 0 mod 9.

Um längere Rechnungen zu vermeiden, rechnen wir:

(37 ⋅ 30) mod 6 ≡ (37 mod 6 ⋅ 30 mod 6) mod 6.

37 mod 6 ≡ 1 mod 6 kann man relativ leicht bestimmen, weil ja 37 = 36 + 1 = 6 ⋅ 6 + 1 ist.

30 mod 6 ≡ 0 mod 6 kann man relativ leicht bestimmen, weil ja 30 = 30 + 0 = 5 ⋅ 6 + 0 ist.

Somit gilt:

(37 ⋅ 30) mod 6 ≡ (1 ⋅ 0) mod 6 ≡ 0 mod 6.

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

2: 215²=215¹⁺¹=215¹⋅215¹ ≡ 215⋅215=46225 ≡ 135 mod 419

4: 215⁴=215²⁺²=215²⋅215² ≡ 135⋅135=18225 ≡ 208 mod 419

8: 215⁸=215⁴⁺⁴=215⁴⋅215⁴ ≡ 208⋅208=43264 ≡ 107 mod 419

16: 215¹⁶=215⁸⁺⁸=215⁸⋅215⁸ ≡ 107⋅107=11449 ≡ 136 mod 419

32: 215³²=215¹⁶⁺¹⁶=215¹⁶⋅215¹⁶ ≡ 136⋅136=18496 ≡ 60 mod 419

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

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

237 = 128+64+32+8+4+1

153²³⁷

= 153^{128+64+32+8+4+1}

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

≡ 382 ⋅ 36 ⋅ 451 ⋅ 24 ⋅ 350 ⋅ 153 mod 457
≡ 13752 ⋅ 451 ⋅ 24 ⋅ 350 ⋅ 153 mod 457 ≡ 42 ⋅ 451 ⋅ 24 ⋅ 350 ⋅ 153 mod 457
≡ 18942 ⋅ 24 ⋅ 350 ⋅ 153 mod 457 ≡ 205 ⋅ 24 ⋅ 350 ⋅ 153 mod 457
≡ 4920 ⋅ 350 ⋅ 153 mod 457 ≡ 350 ⋅ 350 ⋅ 153 mod 457
≡ 122500 ⋅ 153 mod 457 ≡ 24 ⋅ 153 mod 457
≡ 3672 mod 457 ≡ 16 mod 457

Es gilt also: 153²³⁷ ≡ 16 mod 457

Berechnung des größten gemeinsamen Teilers von 79 und 74

=>79	= 1⋅74 + 5
=>74	= 14⋅5 + 4
=>5	= 1⋅4 + 1
=>4	= 4⋅1 + 0

also gilt: ggt(79,74)=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= 5-1⋅4
4= 74-14⋅5	eingesetzt in die Zeile drüber:	1	= 1⋅5 -1⋅(74 -14⋅ 5) = 1⋅5 -1⋅74 +14⋅ 5) = -1⋅74 +15⋅ 5 (=1)
5= 79-1⋅74	eingesetzt in die Zeile drüber:	1	= -1⋅74 +15⋅(79 -1⋅ 74) = -1⋅74 +15⋅79 -15⋅ 74) = 15⋅79 -16⋅ 74 (=1)

Es gilt also: ggt(79,74)=1 = 15⋅79 -16⋅74

oder wenn man 15⋅79 auf die linke Seite bringt:

1 -15⋅79 = -16⋅74

-16⋅74 = -15⋅79 + 1 |+79⋅74

-16⋅74 + 79⋅74 = -15⋅79 + 79⋅74 + 1

(-16 + 79) ⋅ 74 = (-15 + 74) ⋅ 79 + 1

63⋅74 = 59⋅79 + 1

Es gilt also: 63⋅74 = 59⋅79 +1

Somit 63⋅74 = 1 mod 79

63 ist also das Inverse von 74 mod 79