Um längere Rechnungen zu vermeiden, rechnen wir:

(18005 + 2999) mod 6 ≡ (18005 mod 6 + 2999 mod 6) mod 6.

18005 mod 6 ≡ 5 mod 6 kann man relativ leicht bestimmen, weil ja 18005 = 18000+5 = 6 ⋅ 3000 +5.

2999 mod 6 ≡ 5 mod 6 kann man relativ leicht bestimmen, weil ja 2999 = 3000-1 = 6 ⋅ 500 -1 = 6 ⋅ 500 - 6 + 5.

Somit gilt:

(18005 + 2999) mod 6 ≡ (5 + 5) mod 6 ≡ 10 mod 6 ≡ 4 mod 6.

Um längere Rechnungen zu vermeiden, rechnen wir:

(43 ⋅ 93) mod 6 ≡ (43 mod 6 ⋅ 93 mod 6) mod 6.

43 mod 6 ≡ 1 mod 6 kann man relativ leicht bestimmen, weil ja 43 = 42 + 1 = 7 ⋅ 6 + 1 ist.

93 mod 6 ≡ 3 mod 6 kann man relativ leicht bestimmen, weil ja 93 = 90 + 3 = 15 ⋅ 6 + 3 ist.

Somit gilt:

(43 ⋅ 93) mod 6 ≡ (1 ⋅ 3) mod 6 ≡ 3 mod 6.

Die 16 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: 149¹=149

2: 149²=149¹⁺¹=149¹⋅149¹ ≡ 149⋅149=22201 ≡ 46 mod 211

4: 149⁴=149²⁺²=149²⋅149² ≡ 46⋅46=2116 ≡ 6 mod 211

8: 149⁸=149⁴⁺⁴=149⁴⋅149⁴ ≡ 6⋅6=36 ≡ 36 mod 211

16: 149¹⁶=149⁸⁺⁸=149⁸⋅149⁸ ≡ 36⋅36=1296 ≡ 30 mod 211

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

595²³⁷

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

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

≡ 506 ⋅ 922 ⋅ 561 ⋅ 58 ⋅ 803 ⋅ 595 mod 1009
≡ 466532 ⋅ 561 ⋅ 58 ⋅ 803 ⋅ 595 mod 1009 ≡ 374 ⋅ 561 ⋅ 58 ⋅ 803 ⋅ 595 mod 1009
≡ 209814 ⋅ 58 ⋅ 803 ⋅ 595 mod 1009 ≡ 951 ⋅ 58 ⋅ 803 ⋅ 595 mod 1009
≡ 55158 ⋅ 803 ⋅ 595 mod 1009 ≡ 672 ⋅ 803 ⋅ 595 mod 1009
≡ 539616 ⋅ 595 mod 1009 ≡ 810 ⋅ 595 mod 1009
≡ 481950 mod 1009 ≡ 657 mod 1009

Es gilt also: 595²³⁷ ≡ 657 mod 1009

Berechnung des größten gemeinsamen Teilers von 71 und 25

=>71	= 2⋅25 + 21
=>25	= 1⋅21 + 4
=>21	= 5⋅4 + 1
=>4	= 4⋅1 + 0

also gilt: ggt(71,25)=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= 21-5⋅4
4= 25-1⋅21	eingesetzt in die Zeile drüber:	1	= 1⋅21 -5⋅(25 -1⋅ 21) = 1⋅21 -5⋅25 +5⋅ 21) = -5⋅25 +6⋅ 21 (=1)
21= 71-2⋅25	eingesetzt in die Zeile drüber:	1	= -5⋅25 +6⋅(71 -2⋅ 25) = -5⋅25 +6⋅71 -12⋅ 25) = 6⋅71 -17⋅ 25 (=1)

Es gilt also: ggt(71,25)=1 = 6⋅71 -17⋅25

oder wenn man 6⋅71 auf die linke Seite bringt:

1 -6⋅71 = -17⋅25

-17⋅25 = -6⋅71 + 1 |+71⋅25

-17⋅25 + 71⋅25 = -6⋅71 + 71⋅25 + 1

(-17 + 71) ⋅ 25 = (-6 + 25) ⋅ 71 + 1

54⋅25 = 19⋅71 + 1

Es gilt also: 54⋅25 = 19⋅71 +1

Somit 54⋅25 = 1 mod 71

54 ist also das Inverse von 25 mod 71