Um längere Rechnungen zu vermeiden, rechnen wir:

(20000 + 164) mod 4 ≡ (20000 mod 4 + 164 mod 4) mod 4.

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

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

Somit gilt:

(20000 + 164) mod 4 ≡ (0 + 0) mod 4 ≡ 0 mod 4.

Um längere Rechnungen zu vermeiden, rechnen wir:

(39 ⋅ 33) mod 6 ≡ (39 mod 6 ⋅ 33 mod 6) mod 6.

39 mod 6 ≡ 3 mod 6 kann man relativ leicht bestimmen, weil ja 39 = 36 + 3 = 6 ⋅ 6 + 3 ist.

33 mod 6 ≡ 3 mod 6 kann man relativ leicht bestimmen, weil ja 33 = 30 + 3 = 5 ⋅ 6 + 3 ist.

Somit gilt:

(39 ⋅ 33) mod 6 ≡ (3 ⋅ 3) mod 6 ≡ 9 mod 6 ≡ 3 mod 6.

Die 32 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: 299¹=299

2: 299²=299¹⁺¹=299¹⋅299¹ ≡ 299⋅299=89401 ≡ 162 mod 383

4: 299⁴=299²⁺²=299²⋅299² ≡ 162⋅162=26244 ≡ 200 mod 383

8: 299⁸=299⁴⁺⁴=299⁴⋅299⁴ ≡ 200⋅200=40000 ≡ 168 mod 383

16: 299¹⁶=299⁸⁺⁸=299⁸⋅299⁸ ≡ 168⋅168=28224 ≡ 265 mod 383

32: 299³²=299¹⁶⁺¹⁶=299¹⁶⋅299¹⁶ ≡ 265⋅265=70225 ≡ 136 mod 383

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

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

189 = 128+32+16+8+4+1

515¹⁸⁹

= 515^{128+32+16+8+4+1}

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

≡ 256 ⋅ 4 ⋅ 615 ⋅ 574 ⋅ 438 ⋅ 515 mod 617
≡ 1024 ⋅ 615 ⋅ 574 ⋅ 438 ⋅ 515 mod 617 ≡ 407 ⋅ 615 ⋅ 574 ⋅ 438 ⋅ 515 mod 617
≡ 250305 ⋅ 574 ⋅ 438 ⋅ 515 mod 617 ≡ 420 ⋅ 574 ⋅ 438 ⋅ 515 mod 617
≡ 241080 ⋅ 438 ⋅ 515 mod 617 ≡ 450 ⋅ 438 ⋅ 515 mod 617
≡ 197100 ⋅ 515 mod 617 ≡ 277 ⋅ 515 mod 617
≡ 142655 mod 617 ≡ 128 mod 617

Es gilt also: 515¹⁸⁹ ≡ 128 mod 617

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

=>61	= 1⋅45 + 16
=>45	= 2⋅16 + 13
=>16	= 1⋅13 + 3
=>13	= 4⋅3 + 1
=>3	= 3⋅1 + 0

also gilt: ggt(61,45)=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= 13-4⋅3
3= 16-1⋅13	eingesetzt in die Zeile drüber:	1	= 1⋅13 -4⋅(16 -1⋅ 13) = 1⋅13 -4⋅16 +4⋅ 13) = -4⋅16 +5⋅ 13 (=1)
13= 45-2⋅16	eingesetzt in die Zeile drüber:	1	= -4⋅16 +5⋅(45 -2⋅ 16) = -4⋅16 +5⋅45 -10⋅ 16) = 5⋅45 -14⋅ 16 (=1)
16= 61-1⋅45	eingesetzt in die Zeile drüber:	1	= 5⋅45 -14⋅(61 -1⋅ 45) = 5⋅45 -14⋅61 +14⋅ 45) = -14⋅61 +19⋅ 45 (=1)

Es gilt also: ggt(61,45)=1 = -14⋅61 +19⋅45

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

1 +14⋅61 = +19⋅45

Es gilt also: 19⋅45 = 14⋅61 +1

Somit 19⋅45 = 1 mod 61

19 ist also das Inverse von 45 mod 61