Um längere Rechnungen zu vermeiden, rechnen wir:

(12003 + 31) mod 3 ≡ (12003 mod 3 + 31 mod 3) mod 3.

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

31 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 31 = 30+1 = 3 ⋅ 10 +1.

Somit gilt:

(12003 + 31) mod 3 ≡ (0 + 1) mod 3 ≡ 1 mod 3.

Um längere Rechnungen zu vermeiden, rechnen wir:

(42 ⋅ 19) mod 9 ≡ (42 mod 9 ⋅ 19 mod 9) mod 9.

42 mod 9 ≡ 6 mod 9 kann man relativ leicht bestimmen, weil ja 42 = 36 + 6 = 4 ⋅ 9 + 6 ist.

19 mod 9 ≡ 1 mod 9 kann man relativ leicht bestimmen, weil ja 19 = 18 + 1 = 2 ⋅ 9 + 1 ist.

Somit gilt:

(42 ⋅ 19) mod 9 ≡ (6 ⋅ 1) mod 9 ≡ 6 mod 9.

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

2: 292²=292¹⁺¹=292¹⋅292¹ ≡ 292⋅292=85264 ≡ 120 mod 367

4: 292⁴=292²⁺²=292²⋅292² ≡ 120⋅120=14400 ≡ 87 mod 367

8: 292⁸=292⁴⁺⁴=292⁴⋅292⁴ ≡ 87⋅87=7569 ≡ 229 mod 367

16: 292¹⁶=292⁸⁺⁸=292⁸⋅292⁸ ≡ 229⋅229=52441 ≡ 327 mod 367

32: 292³²=292¹⁶⁺¹⁶=292¹⁶⋅292¹⁶ ≡ 327⋅327=106929 ≡ 132 mod 367

64: 292⁶⁴=292³²⁺³²=292³²⋅292³² ≡ 132⋅132=17424 ≡ 175 mod 367

128: 292¹²⁸=292⁶⁴⁺⁶⁴=292⁶⁴⋅292⁶⁴ ≡ 175⋅175=30625 ≡ 164 mod 367

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

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

77 = 64+8+4+1

298⁷⁷

= 298^64+8+4+1

= 298⁶⁴⋅298⁸⋅298⁴⋅298¹

≡ 67 ⋅ 269 ⋅ 96 ⋅ 298 mod 389
≡ 18023 ⋅ 96 ⋅ 298 mod 389 ≡ 129 ⋅ 96 ⋅ 298 mod 389
≡ 12384 ⋅ 298 mod 389 ≡ 325 ⋅ 298 mod 389
≡ 96850 mod 389 ≡ 378 mod 389

Es gilt also: 298⁷⁷ ≡ 378 mod 389

Berechnung des größten gemeinsamen Teilers von 101 und 60

=>101	= 1⋅60 + 41
=>60	= 1⋅41 + 19
=>41	= 2⋅19 + 3
=>19	= 6⋅3 + 1
=>3	= 3⋅1 + 0

also gilt: ggt(101,60)=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= 19-6⋅3
3= 41-2⋅19	eingesetzt in die Zeile drüber:	1	= 1⋅19 -6⋅(41 -2⋅ 19) = 1⋅19 -6⋅41 +12⋅ 19) = -6⋅41 +13⋅ 19 (=1)
19= 60-1⋅41	eingesetzt in die Zeile drüber:	1	= -6⋅41 +13⋅(60 -1⋅ 41) = -6⋅41 +13⋅60 -13⋅ 41) = 13⋅60 -19⋅ 41 (=1)
41= 101-1⋅60	eingesetzt in die Zeile drüber:	1	= 13⋅60 -19⋅(101 -1⋅ 60) = 13⋅60 -19⋅101 +19⋅ 60) = -19⋅101 +32⋅ 60 (=1)

Es gilt also: ggt(101,60)=1 = -19⋅101 +32⋅60

oder wenn man -19⋅101 auf die linke Seite bringt:

1 +19⋅101 = +32⋅60

Es gilt also: 32⋅60 = 19⋅101 +1

Somit 32⋅60 = 1 mod 101

32 ist also das Inverse von 60 mod 101