Um längere Rechnungen zu vermeiden, rechnen wir:

(1402 - 3499) mod 7 ≡ (1402 mod 7 - 3499 mod 7) mod 7.

1402 mod 7 ≡ 2 mod 7 kann man relativ leicht bestimmen, weil ja 1402 = 1400+2 = 7 ⋅ 200 +2.

3499 mod 7 ≡ 6 mod 7 kann man relativ leicht bestimmen, weil ja 3499 = 3500-1 = 7 ⋅ 500 -1 = 7 ⋅ 500 - 7 + 6.

Somit gilt:

(1402 - 3499) mod 7 ≡ (2 - 6) mod 7 ≡ -4 mod 7 ≡ 3 mod 7.

Um längere Rechnungen zu vermeiden, rechnen wir:

(28 ⋅ 16) mod 9 ≡ (28 mod 9 ⋅ 16 mod 9) mod 9.

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

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

Somit gilt:

(28 ⋅ 16) mod 9 ≡ (1 ⋅ 7) mod 9 ≡ 7 mod 9.

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

2: 814²=814¹⁺¹=814¹⋅814¹ ≡ 814⋅814=662596 ≡ 132 mod 941

4: 814⁴=814²⁺²=814²⋅814² ≡ 132⋅132=17424 ≡ 486 mod 941

8: 814⁸=814⁴⁺⁴=814⁴⋅814⁴ ≡ 486⋅486=236196 ≡ 5 mod 941

16: 814¹⁶=814⁸⁺⁸=814⁸⋅814⁸ ≡ 5⋅5=25 ≡ 25 mod 941

32: 814³²=814¹⁶⁺¹⁶=814¹⁶⋅814¹⁶ ≡ 25⋅25=625 ≡ 625 mod 941

64: 814⁶⁴=814³²⁺³²=814³²⋅814³² ≡ 625⋅625=390625 ≡ 110 mod 941

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

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

171 = 128+32+8+2+1

152¹⁷¹

= 152^128+32+8+2+1

= 152¹²⁸⋅152³²⋅152⁸⋅152²⋅152¹

≡ 26 ⋅ 256 ⋅ 333 ⋅ 188 ⋅ 152 mod 337
≡ 6656 ⋅ 333 ⋅ 188 ⋅ 152 mod 337 ≡ 253 ⋅ 333 ⋅ 188 ⋅ 152 mod 337
≡ 84249 ⋅ 188 ⋅ 152 mod 337 ≡ 336 ⋅ 188 ⋅ 152 mod 337
≡ 63168 ⋅ 152 mod 337 ≡ 149 ⋅ 152 mod 337
≡ 22648 mod 337 ≡ 69 mod 337

Es gilt also: 152¹⁷¹ ≡ 69 mod 337

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

=>89	= 2⋅31 + 27
=>31	= 1⋅27 + 4
=>27	= 6⋅4 + 3
=>4	= 1⋅3 + 1
=>3	= 3⋅1 + 0

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

Es gilt also: ggt(89,31)=1 = -8⋅89 +23⋅31

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

1 +8⋅89 = +23⋅31

Es gilt also: 23⋅31 = 8⋅89 +1

Somit 23⋅31 = 1 mod 89

23 ist also das Inverse von 31 mod 89