Um längere Rechnungen zu vermeiden, rechnen wir:

(123 - 12003) mod 3 ≡ (123 mod 3 - 12003 mod 3) mod 3.

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

12003 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 12003 = 12000+3 = 3 ⋅ 4000 +3.

Somit gilt:

(123 - 12003) mod 3 ≡ (0 - 0) mod 3 ≡ 0 mod 3.

Um längere Rechnungen zu vermeiden, rechnen wir:

(77 ⋅ 25) mod 10 ≡ (77 mod 10 ⋅ 25 mod 10) mod 10.

77 mod 10 ≡ 7 mod 10 kann man relativ leicht bestimmen, weil ja 77 = 70 + 7 = 7 ⋅ 10 + 7 ist.

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

Somit gilt:

(77 ⋅ 25) mod 10 ≡ (7 ⋅ 5) mod 10 ≡ 35 mod 10 ≡ 5 mod 10.

Die 8 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: 281¹=281

2: 281²=281¹⁺¹=281¹⋅281¹ ≡ 281⋅281=78961 ≡ 383 mod 389

4: 281⁴=281²⁺²=281²⋅281² ≡ 383⋅383=146689 ≡ 36 mod 389

8: 281⁸=281⁴⁺⁴=281⁴⋅281⁴ ≡ 36⋅36=1296 ≡ 129 mod 389

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

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

222 = 128+64+16+8+4+2

415²²²

= 415^{128+64+16+8+4+2}

= 415¹²⁸⋅415⁶⁴⋅415¹⁶⋅415⁸⋅415⁴⋅415²

≡ 205 ⋅ 494 ⋅ 660 ⋅ 502 ⋅ 270 ⋅ 109 mod 683
≡ 101270 ⋅ 660 ⋅ 502 ⋅ 270 ⋅ 109 mod 683 ≡ 186 ⋅ 660 ⋅ 502 ⋅ 270 ⋅ 109 mod 683
≡ 122760 ⋅ 502 ⋅ 270 ⋅ 109 mod 683 ≡ 503 ⋅ 502 ⋅ 270 ⋅ 109 mod 683
≡ 252506 ⋅ 270 ⋅ 109 mod 683 ≡ 479 ⋅ 270 ⋅ 109 mod 683
≡ 129330 ⋅ 109 mod 683 ≡ 243 ⋅ 109 mod 683
≡ 26487 mod 683 ≡ 533 mod 683

Es gilt also: 415²²² ≡ 533 mod 683

Berechnung des größten gemeinsamen Teilers von 97 und 66

=>97	= 1⋅66 + 31
=>66	= 2⋅31 + 4
=>31	= 7⋅4 + 3
=>4	= 1⋅3 + 1
=>3	= 3⋅1 + 0

also gilt: ggt(97,66)=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= 4-1⋅3
3= 31-7⋅4	eingesetzt in die Zeile drüber:	1	= 1⋅4 -1⋅(31 -7⋅ 4) = 1⋅4 -1⋅31 +7⋅ 4) = -1⋅31 +8⋅ 4 (=1)
4= 66-2⋅31	eingesetzt in die Zeile drüber:	1	= -1⋅31 +8⋅(66 -2⋅ 31) = -1⋅31 +8⋅66 -16⋅ 31) = 8⋅66 -17⋅ 31 (=1)
31= 97-1⋅66	eingesetzt in die Zeile drüber:	1	= 8⋅66 -17⋅(97 -1⋅ 66) = 8⋅66 -17⋅97 +17⋅ 66) = -17⋅97 +25⋅ 66 (=1)

Es gilt also: ggt(97,66)=1 = -17⋅97 +25⋅66

oder wenn man -17⋅97 auf die linke Seite bringt:

1 +17⋅97 = +25⋅66

Es gilt also: 25⋅66 = 17⋅97 +1

Somit 25⋅66 = 1 mod 97

25 ist also das Inverse von 66 mod 97