Um längere Rechnungen zu vermeiden, rechnen wir:

(3598 - 3601) mod 9 ≡ (3598 mod 9 - 3601 mod 9) mod 9.

3598 mod 9 ≡ 7 mod 9 kann man relativ leicht bestimmen, weil ja 3598 = 3600-2 = 9 ⋅ 400 -2 = 9 ⋅ 400 - 9 + 7.

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

Somit gilt:

(3598 - 3601) mod 9 ≡ (7 - 1) mod 9 ≡ 6 mod 9.

Um längere Rechnungen zu vermeiden, rechnen wir:

(88 ⋅ 20) mod 9 ≡ (88 mod 9 ⋅ 20 mod 9) mod 9.

88 mod 9 ≡ 7 mod 9 kann man relativ leicht bestimmen, weil ja 88 = 81 + 7 = 9 ⋅ 9 + 7 ist.

20 mod 9 ≡ 2 mod 9 kann man relativ leicht bestimmen, weil ja 20 = 18 + 2 = 2 ⋅ 9 + 2 ist.

Somit gilt:

(88 ⋅ 20) mod 9 ≡ (7 ⋅ 2) mod 9 ≡ 14 mod 9 ≡ 5 mod 9.

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

2: 228²=228¹⁺¹=228¹⋅228¹ ≡ 228⋅228=51984 ≡ 123 mod 293

4: 228⁴=228²⁺²=228²⋅228² ≡ 123⋅123=15129 ≡ 186 mod 293

8: 228⁸=228⁴⁺⁴=228⁴⋅228⁴ ≡ 186⋅186=34596 ≡ 22 mod 293

16: 228¹⁶=228⁸⁺⁸=228⁸⋅228⁸ ≡ 22⋅22=484 ≡ 191 mod 293

32: 228³²=228¹⁶⁺¹⁶=228¹⁶⋅228¹⁶ ≡ 191⋅191=36481 ≡ 149 mod 293

64: 228⁶⁴=228³²⁺³²=228³²⋅228³² ≡ 149⋅149=22201 ≡ 226 mod 293

128: 228¹²⁸=228⁶⁴⁺⁶⁴=228⁶⁴⋅228⁶⁴ ≡ 226⋅226=51076 ≡ 94 mod 293

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

229²⁴²

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

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

≡ 51 ⋅ 135 ⋅ 64 ⋅ 8 ⋅ 16 mod 233
≡ 6885 ⋅ 64 ⋅ 8 ⋅ 16 mod 233 ≡ 128 ⋅ 64 ⋅ 8 ⋅ 16 mod 233
≡ 8192 ⋅ 8 ⋅ 16 mod 233 ≡ 37 ⋅ 8 ⋅ 16 mod 233
≡ 296 ⋅ 16 mod 233 ≡ 63 ⋅ 16 mod 233
≡ 1008 mod 233 ≡ 76 mod 233

Es gilt also: 229²⁴² ≡ 76 mod 233

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

=>83	= 1⋅54 + 29
=>54	= 1⋅29 + 25
=>29	= 1⋅25 + 4
=>25	= 6⋅4 + 1
=>4	= 4⋅1 + 0

also gilt: ggt(83,54)=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= 25-6⋅4
4= 29-1⋅25	eingesetzt in die Zeile drüber:	1	= 1⋅25 -6⋅(29 -1⋅ 25) = 1⋅25 -6⋅29 +6⋅ 25) = -6⋅29 +7⋅ 25 (=1)
25= 54-1⋅29	eingesetzt in die Zeile drüber:	1	= -6⋅29 +7⋅(54 -1⋅ 29) = -6⋅29 +7⋅54 -7⋅ 29) = 7⋅54 -13⋅ 29 (=1)
29= 83-1⋅54	eingesetzt in die Zeile drüber:	1	= 7⋅54 -13⋅(83 -1⋅ 54) = 7⋅54 -13⋅83 +13⋅ 54) = -13⋅83 +20⋅ 54 (=1)

Es gilt also: ggt(83,54)=1 = -13⋅83 +20⋅54

oder wenn man -13⋅83 auf die linke Seite bringt:

1 +13⋅83 = +20⋅54

Es gilt also: 20⋅54 = 13⋅83 +1

Somit 20⋅54 = 1 mod 83

20 ist also das Inverse von 54 mod 83