Um längere Rechnungen zu vermeiden, rechnen wir:

(20001 + 399) mod 4 ≡ (20001 mod 4 + 399 mod 4) mod 4.

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

399 mod 4 ≡ 3 mod 4 kann man relativ leicht bestimmen, weil ja 399 = 300+99 = 4 ⋅ 75 +99.

Somit gilt:

(20001 + 399) mod 4 ≡ (1 + 3) mod 4 ≡ 4 mod 4 ≡ 0 mod 4.

Um längere Rechnungen zu vermeiden, rechnen wir:

(69 ⋅ 20) mod 10 ≡ (69 mod 10 ⋅ 20 mod 10) mod 10.

69 mod 10 ≡ 9 mod 10 kann man relativ leicht bestimmen, weil ja 69 = 60 + 9 = 6 ⋅ 10 + 9 ist.

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

Somit gilt:

(69 ⋅ 20) mod 10 ≡ (9 ⋅ 0) mod 10 ≡ 0 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: 584¹=584

2: 584²=584¹⁺¹=584¹⋅584¹ ≡ 584⋅584=341056 ≡ 337 mod 829

4: 584⁴=584²⁺²=584²⋅584² ≡ 337⋅337=113569 ≡ 825 mod 829

8: 584⁸=584⁴⁺⁴=584⁴⋅584⁴ ≡ 825⋅825=680625 ≡ 16 mod 829

16: 584¹⁶=584⁸⁺⁸=584⁸⋅584⁸ ≡ 16⋅16=256 ≡ 256 mod 829

32: 584³²=584¹⁶⁺¹⁶=584¹⁶⋅584¹⁶ ≡ 256⋅256=65536 ≡ 45 mod 829

64: 584⁶⁴=584³²⁺³²=584³²⋅584³² ≡ 45⋅45=2025 ≡ 367 mod 829

128: 584¹²⁸=584⁶⁴⁺⁶⁴=584⁶⁴⋅584⁶⁴ ≡ 367⋅367=134689 ≡ 391 mod 829

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

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

74 = 64+8+2

669⁷⁴

= 669⁶⁴⁺⁸⁺²

= 669⁶⁴⋅669⁸⋅669²

≡ 35 ⋅ 6 ⋅ 700 mod 811
≡ 210 ⋅ 700 mod 811
≡ 147000 mod 811 ≡ 209 mod 811

Es gilt also: 669⁷⁴ ≡ 209 mod 811

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

=>53	= 1⋅30 + 23
=>30	= 1⋅23 + 7
=>23	= 3⋅7 + 2
=>7	= 3⋅2 + 1
=>2	= 2⋅1 + 0

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

Es gilt also: ggt(53,30)=1 = -13⋅53 +23⋅30

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

1 +13⋅53 = +23⋅30

Es gilt also: 23⋅30 = 13⋅53 +1

Somit 23⋅30 = 1 mod 53

23 ist also das Inverse von 30 mod 53