Um längere Rechnungen zu vermeiden, rechnen wir:

(20000 + 397) mod 4 ≡ (20000 mod 4 + 397 mod 4) mod 4.

20000 mod 4 ≡ 0 mod 4 kann man relativ leicht bestimmen, weil ja 20000 = 20000+0 = 4 ⋅ 5000 +0.

397 mod 4 ≡ 1 mod 4 kann man relativ leicht bestimmen, weil ja 397 = 300+97 = 4 ⋅ 75 +97.

Somit gilt:

(20000 + 397) mod 4 ≡ (0 + 1) mod 4 ≡ 1 mod 4.

Um längere Rechnungen zu vermeiden, rechnen wir:

(47 ⋅ 45) mod 11 ≡ (47 mod 11 ⋅ 45 mod 11) mod 11.

47 mod 11 ≡ 3 mod 11 kann man relativ leicht bestimmen, weil ja 47 = 44 + 3 = 4 ⋅ 11 + 3 ist.

45 mod 11 ≡ 1 mod 11 kann man relativ leicht bestimmen, weil ja 45 = 44 + 1 = 4 ⋅ 11 + 1 ist.

Somit gilt:

(47 ⋅ 45) mod 11 ≡ (3 ⋅ 1) mod 11 ≡ 3 mod 11.

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

2: 236²=236¹⁺¹=236¹⋅236¹ ≡ 236⋅236=55696 ≡ 547 mod 593

4: 236⁴=236²⁺²=236²⋅236² ≡ 547⋅547=299209 ≡ 337 mod 593

8: 236⁸=236⁴⁺⁴=236⁴⋅236⁴ ≡ 337⋅337=113569 ≡ 306 mod 593

16: 236¹⁶=236⁸⁺⁸=236⁸⋅236⁸ ≡ 306⋅306=93636 ≡ 535 mod 593

32: 236³²=236¹⁶⁺¹⁶=236¹⁶⋅236¹⁶ ≡ 535⋅535=286225 ≡ 399 mod 593

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

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

223 = 128+64+16+8+4+2+1

197²²³

= 197^{128+64+16+8+4+2+1}

= 197¹²⁸⋅197⁶⁴⋅197¹⁶⋅197⁸⋅197⁴⋅197²⋅197¹

≡ 440 ⋅ 54 ⋅ 49 ⋅ 7 ⋅ 61 ⋅ 431 ⋅ 197 mod 619
≡ 23760 ⋅ 49 ⋅ 7 ⋅ 61 ⋅ 431 ⋅ 197 mod 619 ≡ 238 ⋅ 49 ⋅ 7 ⋅ 61 ⋅ 431 ⋅ 197 mod 619
≡ 11662 ⋅ 7 ⋅ 61 ⋅ 431 ⋅ 197 mod 619 ≡ 520 ⋅ 7 ⋅ 61 ⋅ 431 ⋅ 197 mod 619
≡ 3640 ⋅ 61 ⋅ 431 ⋅ 197 mod 619 ≡ 545 ⋅ 61 ⋅ 431 ⋅ 197 mod 619
≡ 33245 ⋅ 431 ⋅ 197 mod 619 ≡ 438 ⋅ 431 ⋅ 197 mod 619
≡ 188778 ⋅ 197 mod 619 ≡ 602 ⋅ 197 mod 619
≡ 118594 mod 619 ≡ 365 mod 619

Es gilt also: 197²²³ ≡ 365 mod 619

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

=>53	= 2⋅22 + 9
=>22	= 2⋅9 + 4
=>9	= 2⋅4 + 1
=>4	= 4⋅1 + 0

also gilt: ggt(53,22)=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= 22-2⋅9	eingesetzt in die Zeile drüber:	1	= 1⋅9 -2⋅(22 -2⋅ 9) = 1⋅9 -2⋅22 +4⋅ 9) = -2⋅22 +5⋅ 9 (=1)
9= 53-2⋅22	eingesetzt in die Zeile drüber:	1	= -2⋅22 +5⋅(53 -2⋅ 22) = -2⋅22 +5⋅53 -10⋅ 22) = 5⋅53 -12⋅ 22 (=1)

Es gilt also: ggt(53,22)=1 = 5⋅53 -12⋅22

oder wenn man 5⋅53 auf die linke Seite bringt:

1 -5⋅53 = -12⋅22

-12⋅22 = -5⋅53 + 1 |+53⋅22

-12⋅22 + 53⋅22 = -5⋅53 + 53⋅22 + 1

(-12 + 53) ⋅ 22 = (-5 + 22) ⋅ 53 + 1

41⋅22 = 17⋅53 + 1

Es gilt also: 41⋅22 = 17⋅53 +1

Somit 41⋅22 = 1 mod 53

41 ist also das Inverse von 22 mod 53