Um längere Rechnungen zu vermeiden, rechnen wir:

(450 - 2693) mod 9 ≡ (450 mod 9 - 2693 mod 9) mod 9.

450 mod 9 ≡ 0 mod 9 kann man relativ leicht bestimmen, weil ja 450 = 450+0 = 9 ⋅ 50 +0.

2693 mod 9 ≡ 2 mod 9 kann man relativ leicht bestimmen, weil ja 2693 = 2700-7 = 9 ⋅ 300 -7 = 9 ⋅ 300 - 9 + 2.

Somit gilt:

(450 - 2693) mod 9 ≡ (0 - 2) mod 9 ≡ -2 mod 9 ≡ 7 mod 9.

Um längere Rechnungen zu vermeiden, rechnen wir:

(66 ⋅ 50) mod 7 ≡ (66 mod 7 ⋅ 50 mod 7) mod 7.

66 mod 7 ≡ 3 mod 7 kann man relativ leicht bestimmen, weil ja 66 = 63 + 3 = 9 ⋅ 7 + 3 ist.

50 mod 7 ≡ 1 mod 7 kann man relativ leicht bestimmen, weil ja 50 = 49 + 1 = 7 ⋅ 7 + 1 ist.

Somit gilt:

(66 ⋅ 50) mod 7 ≡ (3 ⋅ 1) mod 7 ≡ 3 mod 7.

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

2: 440²=440¹⁺¹=440¹⋅440¹ ≡ 440⋅440=193600 ≡ 189 mod 719

4: 440⁴=440²⁺²=440²⋅440² ≡ 189⋅189=35721 ≡ 490 mod 719

8: 440⁸=440⁴⁺⁴=440⁴⋅440⁴ ≡ 490⋅490=240100 ≡ 673 mod 719

16: 440¹⁶=440⁸⁺⁸=440⁸⋅440⁸ ≡ 673⋅673=452929 ≡ 678 mod 719

32: 440³²=440¹⁶⁺¹⁶=440¹⁶⋅440¹⁶ ≡ 678⋅678=459684 ≡ 243 mod 719

64: 440⁶⁴=440³²⁺³²=440³²⋅440³² ≡ 243⋅243=59049 ≡ 91 mod 719

128: 440¹²⁸=440⁶⁴⁺⁶⁴=440⁶⁴⋅440⁶⁴ ≡ 91⋅91=8281 ≡ 372 mod 719

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

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

173 = 128+32+8+4+1

468¹⁷³

= 468^128+32+8+4+1

= 468¹²⁸⋅468³²⋅468⁸⋅468⁴⋅468¹

≡ 517 ⋅ 618 ⋅ 223 ⋅ 565 ⋅ 468 mod 673
≡ 319506 ⋅ 223 ⋅ 565 ⋅ 468 mod 673 ≡ 504 ⋅ 223 ⋅ 565 ⋅ 468 mod 673
≡ 112392 ⋅ 565 ⋅ 468 mod 673 ≡ 1 ⋅ 565 ⋅ 468 mod 673
≡ 565 ⋅ 468 mod 673
≡ 264420 mod 673 ≡ 604 mod 673

Es gilt also: 468¹⁷³ ≡ 604 mod 673

Berechnung des größten gemeinsamen Teilers von 83 und 52

=>83	= 1⋅52 + 31
=>52	= 1⋅31 + 21
=>31	= 1⋅21 + 10
=>21	= 2⋅10 + 1
=>10	= 10⋅1 + 0

also gilt: ggt(83,52)=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= 21-2⋅10
10= 31-1⋅21	eingesetzt in die Zeile drüber:	1	= 1⋅21 -2⋅(31 -1⋅ 21) = 1⋅21 -2⋅31 +2⋅ 21) = -2⋅31 +3⋅ 21 (=1)
21= 52-1⋅31	eingesetzt in die Zeile drüber:	1	= -2⋅31 +3⋅(52 -1⋅ 31) = -2⋅31 +3⋅52 -3⋅ 31) = 3⋅52 -5⋅ 31 (=1)
31= 83-1⋅52	eingesetzt in die Zeile drüber:	1	= 3⋅52 -5⋅(83 -1⋅ 52) = 3⋅52 -5⋅83 +5⋅ 52) = -5⋅83 +8⋅ 52 (=1)

Es gilt also: ggt(83,52)=1 = -5⋅83 +8⋅52

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

1 +5⋅83 = +8⋅52

Es gilt also: 8⋅52 = 5⋅83 +1

Somit 8⋅52 = 1 mod 83

8 ist also das Inverse von 52 mod 83