Um längere Rechnungen zu vermeiden, rechnen wir:

(24006 - 175) mod 6 ≡ (24006 mod 6 - 175 mod 6) mod 6.

24006 mod 6 ≡ 0 mod 6 kann man relativ leicht bestimmen, weil ja 24006 = 24000+6 = 6 ⋅ 4000 +6.

175 mod 6 ≡ 1 mod 6 kann man relativ leicht bestimmen, weil ja 175 = 180-5 = 6 ⋅ 30 -5 = 6 ⋅ 30 - 6 + 1.

Somit gilt:

(24006 - 175) mod 6 ≡ (0 - 1) mod 6 ≡ -1 mod 6 ≡ 5 mod 6.

Um längere Rechnungen zu vermeiden, rechnen wir:

(78 ⋅ 32) mod 8 ≡ (78 mod 8 ⋅ 32 mod 8) mod 8.

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

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

Somit gilt:

(78 ⋅ 32) mod 8 ≡ (6 ⋅ 0) mod 8 ≡ 0 mod 8.

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

2: 189²=189¹⁺¹=189¹⋅189¹ ≡ 189⋅189=35721 ≡ 102 mod 383

4: 189⁴=189²⁺²=189²⋅189² ≡ 102⋅102=10404 ≡ 63 mod 383

8: 189⁸=189⁴⁺⁴=189⁴⋅189⁴ ≡ 63⋅63=3969 ≡ 139 mod 383

16: 189¹⁶=189⁸⁺⁸=189⁸⋅189⁸ ≡ 139⋅139=19321 ≡ 171 mod 383

32: 189³²=189¹⁶⁺¹⁶=189¹⁶⋅189¹⁶ ≡ 171⋅171=29241 ≡ 133 mod 383

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

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

242 = 128+64+32+16+2

147²⁴²

= 147^{128+64+32+16+2}

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

≡ 327 ⋅ 248 ⋅ 421 ⋅ 68 ⋅ 127 mod 467
≡ 81096 ⋅ 421 ⋅ 68 ⋅ 127 mod 467 ≡ 305 ⋅ 421 ⋅ 68 ⋅ 127 mod 467
≡ 128405 ⋅ 68 ⋅ 127 mod 467 ≡ 447 ⋅ 68 ⋅ 127 mod 467
≡ 30396 ⋅ 127 mod 467 ≡ 41 ⋅ 127 mod 467
≡ 5207 mod 467 ≡ 70 mod 467

Es gilt also: 147²⁴² ≡ 70 mod 467

Berechnung des größten gemeinsamen Teilers von 89 und 83

=>89	= 1⋅83 + 6
=>83	= 13⋅6 + 5
=>6	= 1⋅5 + 1
=>5	= 5⋅1 + 0

also gilt: ggt(89,83)=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= 6-1⋅5
5= 83-13⋅6	eingesetzt in die Zeile drüber:	1	= 1⋅6 -1⋅(83 -13⋅ 6) = 1⋅6 -1⋅83 +13⋅ 6) = -1⋅83 +14⋅ 6 (=1)
6= 89-1⋅83	eingesetzt in die Zeile drüber:	1	= -1⋅83 +14⋅(89 -1⋅ 83) = -1⋅83 +14⋅89 -14⋅ 83) = 14⋅89 -15⋅ 83 (=1)

Es gilt also: ggt(89,83)=1 = 14⋅89 -15⋅83

oder wenn man 14⋅89 auf die linke Seite bringt:

1 -14⋅89 = -15⋅83

-15⋅83 = -14⋅89 + 1 |+89⋅83

-15⋅83 + 89⋅83 = -14⋅89 + 89⋅83 + 1

(-15 + 89) ⋅ 83 = (-14 + 83) ⋅ 89 + 1

74⋅83 = 69⋅89 + 1

Es gilt also: 74⋅83 = 69⋅89 +1

Somit 74⋅83 = 1 mod 89

74 ist also das Inverse von 83 mod 89