Um längere Rechnungen zu vermeiden, rechnen wir:

(5994 + 18000) mod 6 ≡ (5994 mod 6 + 18000 mod 6) mod 6.

5994 mod 6 ≡ 0 mod 6 kann man relativ leicht bestimmen, weil ja 5994 = 6000-6 = 6 ⋅ 1000 -6 = 6 ⋅ 1000 - 6 + 0.

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

Somit gilt:

(5994 + 18000) mod 6 ≡ (0 + 0) mod 6 ≡ 0 mod 6.

Um längere Rechnungen zu vermeiden, rechnen wir:

(32 ⋅ 27) mod 6 ≡ (32 mod 6 ⋅ 27 mod 6) mod 6.

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

27 mod 6 ≡ 3 mod 6 kann man relativ leicht bestimmen, weil ja 27 = 24 + 3 = 4 ⋅ 6 + 3 ist.

Somit gilt:

(32 ⋅ 27) mod 6 ≡ (2 ⋅ 3) mod 6 ≡ 6 mod 6 ≡ 0 mod 6.

Die 64 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: 740¹=740

2: 740²=740¹⁺¹=740¹⋅740¹ ≡ 740⋅740=547600 ≡ 140 mod 883

4: 740⁴=740²⁺²=740²⋅740² ≡ 140⋅140=19600 ≡ 174 mod 883

8: 740⁸=740⁴⁺⁴=740⁴⋅740⁴ ≡ 174⋅174=30276 ≡ 254 mod 883

16: 740¹⁶=740⁸⁺⁸=740⁸⋅740⁸ ≡ 254⋅254=64516 ≡ 57 mod 883

32: 740³²=740¹⁶⁺¹⁶=740¹⁶⋅740¹⁶ ≡ 57⋅57=3249 ≡ 600 mod 883

64: 740⁶⁴=740³²⁺³²=740³²⋅740³² ≡ 600⋅600=360000 ≡ 619 mod 883

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

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

219 = 128+64+16+8+2+1

319²¹⁹

= 319^{128+64+16+8+2+1}

= 319¹²⁸⋅319⁶⁴⋅319¹⁶⋅319⁸⋅319²⋅319¹

≡ 106 ⋅ 346 ⋅ 40 ⋅ 37 ⋅ 314 ⋅ 319 mod 443
≡ 36676 ⋅ 40 ⋅ 37 ⋅ 314 ⋅ 319 mod 443 ≡ 350 ⋅ 40 ⋅ 37 ⋅ 314 ⋅ 319 mod 443
≡ 14000 ⋅ 37 ⋅ 314 ⋅ 319 mod 443 ≡ 267 ⋅ 37 ⋅ 314 ⋅ 319 mod 443
≡ 9879 ⋅ 314 ⋅ 319 mod 443 ≡ 133 ⋅ 314 ⋅ 319 mod 443
≡ 41762 ⋅ 319 mod 443 ≡ 120 ⋅ 319 mod 443
≡ 38280 mod 443 ≡ 182 mod 443

Es gilt also: 319²¹⁹ ≡ 182 mod 443

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

=>61	= 3⋅18 + 7
=>18	= 2⋅7 + 4
=>7	= 1⋅4 + 3
=>4	= 1⋅3 + 1
=>3	= 3⋅1 + 0

also gilt: ggt(61,18)=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= 7-1⋅4	eingesetzt in die Zeile drüber:	1	= 1⋅4 -1⋅(7 -1⋅ 4) = 1⋅4 -1⋅7 +1⋅ 4) = -1⋅7 +2⋅ 4 (=1)
4= 18-2⋅7	eingesetzt in die Zeile drüber:	1	= -1⋅7 +2⋅(18 -2⋅ 7) = -1⋅7 +2⋅18 -4⋅ 7) = 2⋅18 -5⋅ 7 (=1)
7= 61-3⋅18	eingesetzt in die Zeile drüber:	1	= 2⋅18 -5⋅(61 -3⋅ 18) = 2⋅18 -5⋅61 +15⋅ 18) = -5⋅61 +17⋅ 18 (=1)

Es gilt also: ggt(61,18)=1 = -5⋅61 +17⋅18

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

1 +5⋅61 = +17⋅18

Es gilt also: 17⋅18 = 5⋅61 +1

Somit 17⋅18 = 1 mod 61

17 ist also das Inverse von 18 mod 61