Um längere Rechnungen zu vermeiden, rechnen wir:

(18001 - 1204) mod 6 ≡ (18001 mod 6 - 1204 mod 6) mod 6.

18001 mod 6 ≡ 1 mod 6 kann man relativ leicht bestimmen, weil ja 18001 = 18000+1 = 6 ⋅ 3000 +1.

1204 mod 6 ≡ 4 mod 6 kann man relativ leicht bestimmen, weil ja 1204 = 1200+4 = 6 ⋅ 200 +4.

Somit gilt:

(18001 - 1204) mod 6 ≡ (1 - 4) mod 6 ≡ -3 mod 6 ≡ 3 mod 6.

Um längere Rechnungen zu vermeiden, rechnen wir:

(36 ⋅ 42) mod 7 ≡ (36 mod 7 ⋅ 42 mod 7) mod 7.

36 mod 7 ≡ 1 mod 7 kann man relativ leicht bestimmen, weil ja 36 = 35 + 1 = 5 ⋅ 7 + 1 ist.

42 mod 7 ≡ 0 mod 7 kann man relativ leicht bestimmen, weil ja 42 = 42 + 0 = 6 ⋅ 7 + 0 ist.

Somit gilt:

(36 ⋅ 42) mod 7 ≡ (1 ⋅ 0) mod 7 ≡ 0 mod 7.

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

2: 622²=622¹⁺¹=622¹⋅622¹ ≡ 622⋅622=386884 ≡ 74 mod 823

4: 622⁴=622²⁺²=622²⋅622² ≡ 74⋅74=5476 ≡ 538 mod 823

8: 622⁸=622⁴⁺⁴=622⁴⋅622⁴ ≡ 538⋅538=289444 ≡ 571 mod 823

16: 622¹⁶=622⁸⁺⁸=622⁸⋅622⁸ ≡ 571⋅571=326041 ≡ 133 mod 823

32: 622³²=622¹⁶⁺¹⁶=622¹⁶⋅622¹⁶ ≡ 133⋅133=17689 ≡ 406 mod 823

64: 622⁶⁴=622³²⁺³²=622³²⋅622³² ≡ 406⋅406=164836 ≡ 236 mod 823

128: 622¹²⁸=622⁶⁴⁺⁶⁴=622⁶⁴⋅622⁶⁴ ≡ 236⋅236=55696 ≡ 555 mod 823

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

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

212 = 128+64+16+4

209²¹²

= 209^128+64+16+4

= 209¹²⁸⋅209⁶⁴⋅209¹⁶⋅209⁴

≡ 1 ⋅ 1 ⋅ 576 ⋅ 391 mod 577
≡ 1 ⋅ 576 ⋅ 391 mod 577
≡ 576 ⋅ 391 mod 577
≡ 225216 mod 577 ≡ 186 mod 577

Es gilt also: 209²¹² ≡ 186 mod 577

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

=>83	= 1⋅62 + 21
=>62	= 2⋅21 + 20
=>21	= 1⋅20 + 1
=>20	= 20⋅1 + 0

also gilt: ggt(83,62)=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= 21-1⋅20
20= 62-2⋅21	eingesetzt in die Zeile drüber:	1	= 1⋅21 -1⋅(62 -2⋅ 21) = 1⋅21 -1⋅62 +2⋅ 21) = -1⋅62 +3⋅ 21 (=1)
21= 83-1⋅62	eingesetzt in die Zeile drüber:	1	= -1⋅62 +3⋅(83 -1⋅ 62) = -1⋅62 +3⋅83 -3⋅ 62) = 3⋅83 -4⋅ 62 (=1)

Es gilt also: ggt(83,62)=1 = 3⋅83 -4⋅62

oder wenn man 3⋅83 auf die linke Seite bringt:

1 -3⋅83 = -4⋅62

-4⋅62 = -3⋅83 + 1 |+83⋅62

-4⋅62 + 83⋅62 = -3⋅83 + 83⋅62 + 1

(-4 + 83) ⋅ 62 = (-3 + 62) ⋅ 83 + 1

79⋅62 = 59⋅83 + 1

Es gilt also: 79⋅62 = 59⋅83 +1

Somit 79⋅62 = 1 mod 83

79 ist also das Inverse von 62 mod 83