Um längere Rechnungen zu vermeiden, rechnen wir:

(8007 + 7994) mod 8 ≡ (8007 mod 8 + 7994 mod 8) mod 8.

8007 mod 8 ≡ 7 mod 8 kann man relativ leicht bestimmen, weil ja 8007 = 8000+7 = 8 ⋅ 1000 +7.

7994 mod 8 ≡ 2 mod 8 kann man relativ leicht bestimmen, weil ja 7994 = 7000+994 = 8 ⋅ 875 +994.

Somit gilt:

(8007 + 7994) mod 8 ≡ (7 + 2) mod 8 ≡ 9 mod 8 ≡ 1 mod 8.

Um längere Rechnungen zu vermeiden, rechnen wir:

(72 ⋅ 92) mod 9 ≡ (72 mod 9 ⋅ 92 mod 9) mod 9.

72 mod 9 ≡ 0 mod 9 kann man relativ leicht bestimmen, weil ja 72 = 72 + 0 = 8 ⋅ 9 + 0 ist.

92 mod 9 ≡ 2 mod 9 kann man relativ leicht bestimmen, weil ja 92 = 90 + 2 = 10 ⋅ 9 + 2 ist.

Somit gilt:

(72 ⋅ 92) mod 9 ≡ (0 ⋅ 2) mod 9 ≡ 0 mod 9.

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

2: 525²=525¹⁺¹=525¹⋅525¹ ≡ 525⋅525=275625 ≡ 443 mod 617

4: 525⁴=525²⁺²=525²⋅525² ≡ 443⋅443=196249 ≡ 43 mod 617

8: 525⁸=525⁴⁺⁴=525⁴⋅525⁴ ≡ 43⋅43=1849 ≡ 615 mod 617

16: 525¹⁶=525⁸⁺⁸=525⁸⋅525⁸ ≡ 615⋅615=378225 ≡ 4 mod 617

32: 525³²=525¹⁶⁺¹⁶=525¹⁶⋅525¹⁶ ≡ 4⋅4=16 ≡ 16 mod 617

64: 525⁶⁴=525³²⁺³²=525³²⋅525³² ≡ 16⋅16=256 ≡ 256 mod 617

128: 525¹²⁸=525⁶⁴⁺⁶⁴=525⁶⁴⋅525⁶⁴ ≡ 256⋅256=65536 ≡ 134 mod 617

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

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

231 = 128+64+32+4+2+1

468²³¹

= 468^{128+64+32+4+2+1}

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

≡ 384 ⋅ 383 ⋅ 960 ⋅ 1005 ⋅ 71 ⋅ 468 mod 1009
≡ 147072 ⋅ 960 ⋅ 1005 ⋅ 71 ⋅ 468 mod 1009 ≡ 767 ⋅ 960 ⋅ 1005 ⋅ 71 ⋅ 468 mod 1009
≡ 736320 ⋅ 1005 ⋅ 71 ⋅ 468 mod 1009 ≡ 759 ⋅ 1005 ⋅ 71 ⋅ 468 mod 1009
≡ 762795 ⋅ 71 ⋅ 468 mod 1009 ≡ 1000 ⋅ 71 ⋅ 468 mod 1009
≡ 71000 ⋅ 468 mod 1009 ≡ 370 ⋅ 468 mod 1009
≡ 173160 mod 1009 ≡ 621 mod 1009

Es gilt also: 468²³¹ ≡ 621 mod 1009

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

=>61	= 1⋅40 + 21
=>40	= 1⋅21 + 19
=>21	= 1⋅19 + 2
=>19	= 9⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(61,40)=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= 19-9⋅2
2= 21-1⋅19	eingesetzt in die Zeile drüber:	1	= 1⋅19 -9⋅(21 -1⋅ 19) = 1⋅19 -9⋅21 +9⋅ 19) = -9⋅21 +10⋅ 19 (=1)
19= 40-1⋅21	eingesetzt in die Zeile drüber:	1	= -9⋅21 +10⋅(40 -1⋅ 21) = -9⋅21 +10⋅40 -10⋅ 21) = 10⋅40 -19⋅ 21 (=1)
21= 61-1⋅40	eingesetzt in die Zeile drüber:	1	= 10⋅40 -19⋅(61 -1⋅ 40) = 10⋅40 -19⋅61 +19⋅ 40) = -19⋅61 +29⋅ 40 (=1)

Es gilt also: ggt(61,40)=1 = -19⋅61 +29⋅40

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

1 +19⋅61 = +29⋅40

Es gilt also: 29⋅40 = 19⋅61 +1

Somit 29⋅40 = 1 mod 61

29 ist also das Inverse von 40 mod 61