Um längere Rechnungen zu vermeiden, rechnen wir:

(2997 - 186) mod 6 ≡ (2997 mod 6 - 186 mod 6) mod 6.

2997 mod 6 ≡ 3 mod 6 kann man relativ leicht bestimmen, weil ja 2997 = 3000-3 = 6 ⋅ 500 -3 = 6 ⋅ 500 - 6 + 3.

186 mod 6 ≡ 0 mod 6 kann man relativ leicht bestimmen, weil ja 186 = 180+6 = 6 ⋅ 30 +6.

Somit gilt:

(2997 - 186) mod 6 ≡ (3 - 0) mod 6 ≡ 3 mod 6.

Um längere Rechnungen zu vermeiden, rechnen wir:

(90 ⋅ 85) mod 3 ≡ (90 mod 3 ⋅ 85 mod 3) mod 3.

90 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 90 = 90 + 0 = 30 ⋅ 3 + 0 ist.

85 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 85 = 84 + 1 = 28 ⋅ 3 + 1 ist.

Somit gilt:

(90 ⋅ 85) mod 3 ≡ (0 ⋅ 1) mod 3 ≡ 0 mod 3.

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

2: 559²=559¹⁺¹=559¹⋅559¹ ≡ 559⋅559=312481 ≡ 207 mod 809

4: 559⁴=559²⁺²=559²⋅559² ≡ 207⋅207=42849 ≡ 781 mod 809

8: 559⁸=559⁴⁺⁴=559⁴⋅559⁴ ≡ 781⋅781=609961 ≡ 784 mod 809

16: 559¹⁶=559⁸⁺⁸=559⁸⋅559⁸ ≡ 784⋅784=614656 ≡ 625 mod 809

32: 559³²=559¹⁶⁺¹⁶=559¹⁶⋅559¹⁶ ≡ 625⋅625=390625 ≡ 687 mod 809

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

152¹⁸⁹

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

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

≡ 337 ⋅ 140 ⋅ 217 ⋅ 222 ⋅ 218 ⋅ 152 mod 353
≡ 47180 ⋅ 217 ⋅ 222 ⋅ 218 ⋅ 152 mod 353 ≡ 231 ⋅ 217 ⋅ 222 ⋅ 218 ⋅ 152 mod 353
≡ 50127 ⋅ 222 ⋅ 218 ⋅ 152 mod 353 ≡ 1 ⋅ 222 ⋅ 218 ⋅ 152 mod 353
≡ 222 ⋅ 218 ⋅ 152 mod 353
≡ 48396 ⋅ 152 mod 353 ≡ 35 ⋅ 152 mod 353
≡ 5320 mod 353 ≡ 25 mod 353

Es gilt also: 152¹⁸⁹ ≡ 25 mod 353

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

=>61	= 1⋅42 + 19
=>42	= 2⋅19 + 4
=>19	= 4⋅4 + 3
=>4	= 1⋅3 + 1
=>3	= 3⋅1 + 0

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

Es gilt also: ggt(61,42)=1 = -11⋅61 +16⋅42

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

1 +11⋅61 = +16⋅42

Es gilt also: 16⋅42 = 11⋅61 +1

Somit 16⋅42 = 1 mod 61

16 ist also das Inverse von 42 mod 61