Um längere Rechnungen zu vermeiden, rechnen wir:

(320 + 3197) mod 8 ≡ (320 mod 8 + 3197 mod 8) mod 8.

320 mod 8 ≡ 0 mod 8 kann man relativ leicht bestimmen, weil ja 320 = 320+0 = 8 ⋅ 40 +0.

3197 mod 8 ≡ 5 mod 8 kann man relativ leicht bestimmen, weil ja 3197 = 3200-3 = 8 ⋅ 400 -3 = 8 ⋅ 400 - 8 + 5.

Somit gilt:

(320 + 3197) mod 8 ≡ (0 + 5) mod 8 ≡ 5 mod 8.

Um längere Rechnungen zu vermeiden, rechnen wir:

(24 ⋅ 30) mod 9 ≡ (24 mod 9 ⋅ 30 mod 9) mod 9.

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

30 mod 9 ≡ 3 mod 9 kann man relativ leicht bestimmen, weil ja 30 = 27 + 3 = 3 ⋅ 9 + 3 ist.

Somit gilt:

(24 ⋅ 30) mod 9 ≡ (6 ⋅ 3) mod 9 ≡ 18 mod 9 ≡ 0 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: 239¹=239

2: 239²=239¹⁺¹=239¹⋅239¹ ≡ 239⋅239=57121 ≡ 113 mod 509

4: 239⁴=239²⁺²=239²⋅239² ≡ 113⋅113=12769 ≡ 44 mod 509

8: 239⁸=239⁴⁺⁴=239⁴⋅239⁴ ≡ 44⋅44=1936 ≡ 409 mod 509

16: 239¹⁶=239⁸⁺⁸=239⁸⋅239⁸ ≡ 409⋅409=167281 ≡ 329 mod 509

32: 239³²=239¹⁶⁺¹⁶=239¹⁶⋅239¹⁶ ≡ 329⋅329=108241 ≡ 333 mod 509

64: 239⁶⁴=239³²⁺³²=239³²⋅239³² ≡ 333⋅333=110889 ≡ 436 mod 509

128: 239¹²⁸=239⁶⁴⁺⁶⁴=239⁶⁴⋅239⁶⁴ ≡ 436⋅436=190096 ≡ 239 mod 509

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

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

161 = 128+32+1

638¹⁶¹

= 638^128+32+1

= 638¹²⁸⋅638³²⋅638¹

≡ 421 ⋅ 668 ⋅ 638 mod 887
≡ 281228 ⋅ 638 mod 887 ≡ 49 ⋅ 638 mod 887
≡ 31262 mod 887 ≡ 217 mod 887

Es gilt also: 638¹⁶¹ ≡ 217 mod 887

Berechnung des größten gemeinsamen Teilers von 53 und 20

=>53	= 2⋅20 + 13
=>20	= 1⋅13 + 7
=>13	= 1⋅7 + 6
=>7	= 1⋅6 + 1
=>6	= 6⋅1 + 0

also gilt: ggt(53,20)=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-1⋅6
6= 13-1⋅7	eingesetzt in die Zeile drüber:	1	= 1⋅7 -1⋅(13 -1⋅ 7) = 1⋅7 -1⋅13 +1⋅ 7) = -1⋅13 +2⋅ 7 (=1)
7= 20-1⋅13	eingesetzt in die Zeile drüber:	1	= -1⋅13 +2⋅(20 -1⋅ 13) = -1⋅13 +2⋅20 -2⋅ 13) = 2⋅20 -3⋅ 13 (=1)
13= 53-2⋅20	eingesetzt in die Zeile drüber:	1	= 2⋅20 -3⋅(53 -2⋅ 20) = 2⋅20 -3⋅53 +6⋅ 20) = -3⋅53 +8⋅ 20 (=1)

Es gilt also: ggt(53,20)=1 = -3⋅53 +8⋅20

oder wenn man -3⋅53 auf die linke Seite bringt:

1 +3⋅53 = +8⋅20

Es gilt also: 8⋅20 = 3⋅53 +1

Somit 8⋅20 = 1 mod 53

8 ist also das Inverse von 20 mod 53