Um längere Rechnungen zu vermeiden, rechnen wir:

(184 - 1796) mod 6 ≡ (184 mod 6 - 1796 mod 6) mod 6.

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

1796 mod 6 ≡ 2 mod 6 kann man relativ leicht bestimmen, weil ja 1796 = 1800-4 = 6 ⋅ 300 -4 = 6 ⋅ 300 - 6 + 2.

Somit gilt:

(184 - 1796) mod 6 ≡ (4 - 2) mod 6 ≡ 2 mod 6.

Um längere Rechnungen zu vermeiden, rechnen wir:

(48 ⋅ 33) mod 5 ≡ (48 mod 5 ⋅ 33 mod 5) mod 5.

48 mod 5 ≡ 3 mod 5 kann man relativ leicht bestimmen, weil ja 48 = 45 + 3 = 9 ⋅ 5 + 3 ist.

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

Somit gilt:

(48 ⋅ 33) mod 5 ≡ (3 ⋅ 3) mod 5 ≡ 9 mod 5 ≡ 4 mod 5.

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

2: 389²=389¹⁺¹=389¹⋅389¹ ≡ 389⋅389=151321 ≡ 613 mod 661

4: 389⁴=389²⁺²=389²⋅389² ≡ 613⋅613=375769 ≡ 321 mod 661

8: 389⁸=389⁴⁺⁴=389⁴⋅389⁴ ≡ 321⋅321=103041 ≡ 586 mod 661

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

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

187 = 128+32+16+8+2+1

719¹⁸⁷

= 719^{128+32+16+8+2+1}

= 719¹²⁸⋅719³²⋅719¹⁶⋅719⁸⋅719²⋅719¹

≡ 9 ⋅ 606 ⋅ 359 ⋅ 574 ⋅ 196 ⋅ 719 mod 733
≡ 5454 ⋅ 359 ⋅ 574 ⋅ 196 ⋅ 719 mod 733 ≡ 323 ⋅ 359 ⋅ 574 ⋅ 196 ⋅ 719 mod 733
≡ 115957 ⋅ 574 ⋅ 196 ⋅ 719 mod 733 ≡ 143 ⋅ 574 ⋅ 196 ⋅ 719 mod 733
≡ 82082 ⋅ 196 ⋅ 719 mod 733 ≡ 719 ⋅ 196 ⋅ 719 mod 733
≡ 140924 ⋅ 719 mod 733 ≡ 188 ⋅ 719 mod 733
≡ 135172 mod 733 ≡ 300 mod 733

Es gilt also: 719¹⁸⁷ ≡ 300 mod 733

Berechnung des größten gemeinsamen Teilers von 89 und 69

=>89	= 1⋅69 + 20
=>69	= 3⋅20 + 9
=>20	= 2⋅9 + 2
=>9	= 4⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(89,69)=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= 9-4⋅2
2= 20-2⋅9	eingesetzt in die Zeile drüber:	1	= 1⋅9 -4⋅(20 -2⋅ 9) = 1⋅9 -4⋅20 +8⋅ 9) = -4⋅20 +9⋅ 9 (=1)
9= 69-3⋅20	eingesetzt in die Zeile drüber:	1	= -4⋅20 +9⋅(69 -3⋅ 20) = -4⋅20 +9⋅69 -27⋅ 20) = 9⋅69 -31⋅ 20 (=1)
20= 89-1⋅69	eingesetzt in die Zeile drüber:	1	= 9⋅69 -31⋅(89 -1⋅ 69) = 9⋅69 -31⋅89 +31⋅ 69) = -31⋅89 +40⋅ 69 (=1)

Es gilt also: ggt(89,69)=1 = -31⋅89 +40⋅69

oder wenn man -31⋅89 auf die linke Seite bringt:

1 +31⋅89 = +40⋅69

Es gilt also: 40⋅69 = 31⋅89 +1

Somit 40⋅69 = 1 mod 89

40 ist also das Inverse von 69 mod 89