Um längere Rechnungen zu vermeiden, rechnen wir:

(17992 - 268) mod 9 ≡ (17992 mod 9 - 268 mod 9) mod 9.

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

268 mod 9 ≡ 7 mod 9 kann man relativ leicht bestimmen, weil ja 268 = 270-2 = 9 ⋅ 30 -2 = 9 ⋅ 30 - 9 + 7.

Somit gilt:

(17992 - 268) mod 9 ≡ (1 - 7) mod 9 ≡ -6 mod 9 ≡ 3 mod 9.

Um längere Rechnungen zu vermeiden, rechnen wir:

(41 ⋅ 19) mod 10 ≡ (41 mod 10 ⋅ 19 mod 10) mod 10.

41 mod 10 ≡ 1 mod 10 kann man relativ leicht bestimmen, weil ja 41 = 40 + 1 = 4 ⋅ 10 + 1 ist.

19 mod 10 ≡ 9 mod 10 kann man relativ leicht bestimmen, weil ja 19 = 10 + 9 = 1 ⋅ 10 + 9 ist.

Somit gilt:

(41 ⋅ 19) mod 10 ≡ (1 ⋅ 9) mod 10 ≡ 9 mod 10.

Die 128 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: 423¹=423

2: 423²=423¹⁺¹=423¹⋅423¹ ≡ 423⋅423=178929 ≡ 288 mod 863

4: 423⁴=423²⁺²=423²⋅423² ≡ 288⋅288=82944 ≡ 96 mod 863

8: 423⁸=423⁴⁺⁴=423⁴⋅423⁴ ≡ 96⋅96=9216 ≡ 586 mod 863

16: 423¹⁶=423⁸⁺⁸=423⁸⋅423⁸ ≡ 586⋅586=343396 ≡ 785 mod 863

32: 423³²=423¹⁶⁺¹⁶=423¹⁶⋅423¹⁶ ≡ 785⋅785=616225 ≡ 43 mod 863

64: 423⁶⁴=423³²⁺³²=423³²⋅423³² ≡ 43⋅43=1849 ≡ 123 mod 863

128: 423¹²⁸=423⁶⁴⁺⁶⁴=423⁶⁴⋅423⁶⁴ ≡ 123⋅123=15129 ≡ 458 mod 863

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

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

142 = 128+8+4+2

199¹⁴²

= 199^128+8+4+2

= 199¹²⁸⋅199⁸⋅199⁴⋅199²

≡ 386 ⋅ 380 ⋅ 303 ⋅ 108 mod 541
≡ 146680 ⋅ 303 ⋅ 108 mod 541 ≡ 69 ⋅ 303 ⋅ 108 mod 541
≡ 20907 ⋅ 108 mod 541 ≡ 349 ⋅ 108 mod 541
≡ 37692 mod 541 ≡ 363 mod 541

Es gilt also: 199¹⁴² ≡ 363 mod 541

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

=>89	= 2⋅40 + 9
=>40	= 4⋅9 + 4
=>9	= 2⋅4 + 1
=>4	= 4⋅1 + 0

also gilt: ggt(89,40)=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= 9-2⋅4
4= 40-4⋅9	eingesetzt in die Zeile drüber:	1	= 1⋅9 -2⋅(40 -4⋅ 9) = 1⋅9 -2⋅40 +8⋅ 9) = -2⋅40 +9⋅ 9 (=1)
9= 89-2⋅40	eingesetzt in die Zeile drüber:	1	= -2⋅40 +9⋅(89 -2⋅ 40) = -2⋅40 +9⋅89 -18⋅ 40) = 9⋅89 -20⋅ 40 (=1)

Es gilt also: ggt(89,40)=1 = 9⋅89 -20⋅40

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

1 -9⋅89 = -20⋅40

-20⋅40 = -9⋅89 + 1 |+89⋅40

-20⋅40 + 89⋅40 = -9⋅89 + 89⋅40 + 1

(-20 + 89) ⋅ 40 = (-9 + 40) ⋅ 89 + 1

69⋅40 = 31⋅89 + 1

Es gilt also: 69⋅40 = 31⋅89 +1

Somit 69⋅40 = 1 mod 89

69 ist also das Inverse von 40 mod 89