Um längere Rechnungen zu vermeiden, rechnen wir:

(17999 - 36009) mod 9 ≡ (17999 mod 9 - 36009 mod 9) mod 9.

17999 mod 9 ≡ 8 mod 9 kann man relativ leicht bestimmen, weil ja 17999 = 18000-1 = 9 ⋅ 2000 -1 = 9 ⋅ 2000 - 9 + 8.

36009 mod 9 ≡ 0 mod 9 kann man relativ leicht bestimmen, weil ja 36009 = 36000+9 = 9 ⋅ 4000 +9.

Somit gilt:

(17999 - 36009) mod 9 ≡ (8 - 0) mod 9 ≡ 8 mod 9.

Um längere Rechnungen zu vermeiden, rechnen wir:

(84 ⋅ 83) mod 4 ≡ (84 mod 4 ⋅ 83 mod 4) mod 4.

84 mod 4 ≡ 0 mod 4 kann man relativ leicht bestimmen, weil ja 84 = 84 + 0 = 21 ⋅ 4 + 0 ist.

83 mod 4 ≡ 3 mod 4 kann man relativ leicht bestimmen, weil ja 83 = 80 + 3 = 20 ⋅ 4 + 3 ist.

Somit gilt:

(84 ⋅ 83) mod 4 ≡ (0 ⋅ 3) mod 4 ≡ 0 mod 4.

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

2: 591²=591¹⁺¹=591¹⋅591¹ ≡ 591⋅591=349281 ≡ 71 mod 743

4: 591⁴=591²⁺²=591²⋅591² ≡ 71⋅71=5041 ≡ 583 mod 743

8: 591⁸=591⁴⁺⁴=591⁴⋅591⁴ ≡ 583⋅583=339889 ≡ 338 mod 743

16: 591¹⁶=591⁸⁺⁸=591⁸⋅591⁸ ≡ 338⋅338=114244 ≡ 565 mod 743

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

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

123 = 64+32+16+8+2+1

220¹²³

= 220^{64+32+16+8+2+1}

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

≡ 98 ⋅ 87 ⋅ 91 ⋅ 36 ⋅ 200 ⋅ 220 mod 241
≡ 8526 ⋅ 91 ⋅ 36 ⋅ 200 ⋅ 220 mod 241 ≡ 91 ⋅ 91 ⋅ 36 ⋅ 200 ⋅ 220 mod 241
≡ 8281 ⋅ 36 ⋅ 200 ⋅ 220 mod 241 ≡ 87 ⋅ 36 ⋅ 200 ⋅ 220 mod 241
≡ 3132 ⋅ 200 ⋅ 220 mod 241 ≡ 240 ⋅ 200 ⋅ 220 mod 241
≡ 48000 ⋅ 220 mod 241 ≡ 41 ⋅ 220 mod 241
≡ 9020 mod 241 ≡ 103 mod 241

Es gilt also: 220¹²³ ≡ 103 mod 241

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

=>79	= 1⋅70 + 9
=>70	= 7⋅9 + 7
=>9	= 1⋅7 + 2
=>7	= 3⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(79,70)=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= 7-3⋅2
2= 9-1⋅7	eingesetzt in die Zeile drüber:	1	= 1⋅7 -3⋅(9 -1⋅ 7) = 1⋅7 -3⋅9 +3⋅ 7) = -3⋅9 +4⋅ 7 (=1)
7= 70-7⋅9	eingesetzt in die Zeile drüber:	1	= -3⋅9 +4⋅(70 -7⋅ 9) = -3⋅9 +4⋅70 -28⋅ 9) = 4⋅70 -31⋅ 9 (=1)
9= 79-1⋅70	eingesetzt in die Zeile drüber:	1	= 4⋅70 -31⋅(79 -1⋅ 70) = 4⋅70 -31⋅79 +31⋅ 70) = -31⋅79 +35⋅ 70 (=1)

Es gilt also: ggt(79,70)=1 = -31⋅79 +35⋅70

oder wenn man -31⋅79 auf die linke Seite bringt:

1 +31⋅79 = +35⋅70

Es gilt also: 35⋅70 = 31⋅79 +1

Somit 35⋅70 = 1 mod 79

35 ist also das Inverse von 70 mod 79