Um längere Rechnungen zu vermeiden, rechnen wir:

(19997 - 162) mod 4 ≡ (19997 mod 4 - 162 mod 4) mod 4.

19997 mod 4 ≡ 1 mod 4 kann man relativ leicht bestimmen, weil ja 19997 = 19000+997 = 4 ⋅ 4750 +997.

162 mod 4 ≡ 2 mod 4 kann man relativ leicht bestimmen, weil ja 162 = 160+2 = 4 ⋅ 40 +2.

Somit gilt:

(19997 - 162) mod 4 ≡ (1 - 2) mod 4 ≡ -1 mod 4 ≡ 3 mod 4.

Um längere Rechnungen zu vermeiden, rechnen wir:

(72 ⋅ 37) mod 9 ≡ (72 mod 9 ⋅ 37 mod 9) mod 9.

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

37 mod 9 ≡ 1 mod 9 kann man relativ leicht bestimmen, weil ja 37 = 36 + 1 = 4 ⋅ 9 + 1 ist.

Somit gilt:

(72 ⋅ 37) mod 9 ≡ (0 ⋅ 1) mod 9 ≡ 0 mod 9.

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

2: 239²=239¹⁺¹=239¹⋅239¹ ≡ 239⋅239=57121 ≡ 165 mod 491

4: 239⁴=239²⁺²=239²⋅239² ≡ 165⋅165=27225 ≡ 220 mod 491

8: 239⁸=239⁴⁺⁴=239⁴⋅239⁴ ≡ 220⋅220=48400 ≡ 282 mod 491

16: 239¹⁶=239⁸⁺⁸=239⁸⋅239⁸ ≡ 282⋅282=79524 ≡ 473 mod 491

32: 239³²=239¹⁶⁺¹⁶=239¹⁶⋅239¹⁶ ≡ 473⋅473=223729 ≡ 324 mod 491

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

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

247 = 128+64+32+16+4+2+1

588²⁴⁷

= 588^{128+64+32+16+4+2+1}

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

≡ 538 ⋅ 529 ⋅ 570 ⋅ 152 ⋅ 32 ⋅ 25 ⋅ 588 mod 593
≡ 284602 ⋅ 570 ⋅ 152 ⋅ 32 ⋅ 25 ⋅ 588 mod 593 ≡ 555 ⋅ 570 ⋅ 152 ⋅ 32 ⋅ 25 ⋅ 588 mod 593
≡ 316350 ⋅ 152 ⋅ 32 ⋅ 25 ⋅ 588 mod 593 ≡ 281 ⋅ 152 ⋅ 32 ⋅ 25 ⋅ 588 mod 593
≡ 42712 ⋅ 32 ⋅ 25 ⋅ 588 mod 593 ≡ 16 ⋅ 32 ⋅ 25 ⋅ 588 mod 593
≡ 512 ⋅ 25 ⋅ 588 mod 593
≡ 12800 ⋅ 588 mod 593 ≡ 347 ⋅ 588 mod 593
≡ 204036 mod 593 ≡ 44 mod 593

Es gilt also: 588²⁴⁷ ≡ 44 mod 593

Berechnung des größten gemeinsamen Teilers von 73 und 38

=>73	= 1⋅38 + 35
=>38	= 1⋅35 + 3
=>35	= 11⋅3 + 2
=>3	= 1⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(73,38)=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= 3-1⋅2
2= 35-11⋅3	eingesetzt in die Zeile drüber:	1	= 1⋅3 -1⋅(35 -11⋅ 3) = 1⋅3 -1⋅35 +11⋅ 3) = -1⋅35 +12⋅ 3 (=1)
3= 38-1⋅35	eingesetzt in die Zeile drüber:	1	= -1⋅35 +12⋅(38 -1⋅ 35) = -1⋅35 +12⋅38 -12⋅ 35) = 12⋅38 -13⋅ 35 (=1)
35= 73-1⋅38	eingesetzt in die Zeile drüber:	1	= 12⋅38 -13⋅(73 -1⋅ 38) = 12⋅38 -13⋅73 +13⋅ 38) = -13⋅73 +25⋅ 38 (=1)

Es gilt also: ggt(73,38)=1 = -13⋅73 +25⋅38

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

1 +13⋅73 = +25⋅38

Es gilt also: 25⋅38 = 13⋅73 +1

Somit 25⋅38 = 1 mod 73

25 ist also das Inverse von 38 mod 73