Um längere Rechnungen zu vermeiden, rechnen wir:

(123 + 30005) mod 6 ≡ (123 mod 6 + 30005 mod 6) mod 6.

123 mod 6 ≡ 3 mod 6 kann man relativ leicht bestimmen, weil ja 123 = 120+3 = 6 ⋅ 20 +3.

30005 mod 6 ≡ 5 mod 6 kann man relativ leicht bestimmen, weil ja 30005 = 30000+5 = 6 ⋅ 5000 +5.

Somit gilt:

(123 + 30005) mod 6 ≡ (3 + 5) mod 6 ≡ 8 mod 6 ≡ 2 mod 6.

Um längere Rechnungen zu vermeiden, rechnen wir:

(40 ⋅ 19) mod 4 ≡ (40 mod 4 ⋅ 19 mod 4) mod 4.

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

19 mod 4 ≡ 3 mod 4 kann man relativ leicht bestimmen, weil ja 19 = 16 + 3 = 4 ⋅ 4 + 3 ist.

Somit gilt:

(40 ⋅ 19) mod 4 ≡ (0 ⋅ 3) mod 4 ≡ 0 mod 4.

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

2: 484²=484¹⁺¹=484¹⋅484¹ ≡ 484⋅484=234256 ≡ 561 mod 607

4: 484⁴=484²⁺²=484²⋅484² ≡ 561⋅561=314721 ≡ 295 mod 607

8: 484⁸=484⁴⁺⁴=484⁴⋅484⁴ ≡ 295⋅295=87025 ≡ 224 mod 607

16: 484¹⁶=484⁸⁺⁸=484⁸⋅484⁸ ≡ 224⋅224=50176 ≡ 402 mod 607

32: 484³²=484¹⁶⁺¹⁶=484¹⁶⋅484¹⁶ ≡ 402⋅402=161604 ≡ 142 mod 607

64: 484⁶⁴=484³²⁺³²=484³²⋅484³² ≡ 142⋅142=20164 ≡ 133 mod 607

128: 484¹²⁸=484⁶⁴⁺⁶⁴=484⁶⁴⋅484⁶⁴ ≡ 133⋅133=17689 ≡ 86 mod 607

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

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

183 = 128+32+16+4+2+1

428¹⁸³

= 428^{128+32+16+4+2+1}

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

≡ 431 ⋅ 278 ⋅ 105 ⋅ 745 ⋅ 485 ⋅ 428 mod 977
≡ 119818 ⋅ 105 ⋅ 745 ⋅ 485 ⋅ 428 mod 977 ≡ 624 ⋅ 105 ⋅ 745 ⋅ 485 ⋅ 428 mod 977
≡ 65520 ⋅ 745 ⋅ 485 ⋅ 428 mod 977 ≡ 61 ⋅ 745 ⋅ 485 ⋅ 428 mod 977
≡ 45445 ⋅ 485 ⋅ 428 mod 977 ≡ 503 ⋅ 485 ⋅ 428 mod 977
≡ 243955 ⋅ 428 mod 977 ≡ 682 ⋅ 428 mod 977
≡ 291896 mod 977 ≡ 750 mod 977

Es gilt also: 428¹⁸³ ≡ 750 mod 977

Berechnung des größten gemeinsamen Teilers von 61 und 52

=>61	= 1⋅52 + 9
=>52	= 5⋅9 + 7
=>9	= 1⋅7 + 2
=>7	= 3⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(61,52)=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= 9-1⋅7	eingesetzt in die Zeile drüber:	1	= 1⋅7 -3⋅(9 -1⋅ 7) = 1⋅7 -3⋅9 +3⋅ 7) = -3⋅9 +4⋅ 7 (=1)
7= 52-5⋅9	eingesetzt in die Zeile drüber:	1	= -3⋅9 +4⋅(52 -5⋅ 9) = -3⋅9 +4⋅52 -20⋅ 9) = 4⋅52 -23⋅ 9 (=1)
9= 61-1⋅52	eingesetzt in die Zeile drüber:	1	= 4⋅52 -23⋅(61 -1⋅ 52) = 4⋅52 -23⋅61 +23⋅ 52) = -23⋅61 +27⋅ 52 (=1)

Es gilt also: ggt(61,52)=1 = -23⋅61 +27⋅52

oder wenn man -23⋅61 auf die linke Seite bringt:

1 +23⋅61 = +27⋅52

Es gilt also: 27⋅52 = 23⋅61 +1

Somit 27⋅52 = 1 mod 61

27 ist also das Inverse von 52 mod 61