Um längere Rechnungen zu vermeiden, rechnen wir:

(1791 - 3602) mod 9 ≡ (1791 mod 9 - 3602 mod 9) mod 9.

1791 mod 9 ≡ 0 mod 9 kann man relativ leicht bestimmen, weil ja 1791 = 1800-9 = 9 ⋅ 200 -9 = 9 ⋅ 200 - 9 + 0.

3602 mod 9 ≡ 2 mod 9 kann man relativ leicht bestimmen, weil ja 3602 = 3600+2 = 9 ⋅ 400 +2.

Somit gilt:

(1791 - 3602) mod 9 ≡ (0 - 2) mod 9 ≡ -2 mod 9 ≡ 7 mod 9.

Um längere Rechnungen zu vermeiden, rechnen wir:

(78 ⋅ 89) mod 8 ≡ (78 mod 8 ⋅ 89 mod 8) mod 8.

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

89 mod 8 ≡ 1 mod 8 kann man relativ leicht bestimmen, weil ja 89 = 88 + 1 = 11 ⋅ 8 + 1 ist.

Somit gilt:

(78 ⋅ 89) mod 8 ≡ (6 ⋅ 1) mod 8 ≡ 6 mod 8.

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

2: 93²=93¹⁺¹=93¹⋅93¹ ≡ 93⋅93=8649 ≡ 175 mod 223

4: 93⁴=93²⁺²=93²⋅93² ≡ 175⋅175=30625 ≡ 74 mod 223

8: 93⁸=93⁴⁺⁴=93⁴⋅93⁴ ≡ 74⋅74=5476 ≡ 124 mod 223

16: 93¹⁶=93⁸⁺⁸=93⁸⋅93⁸ ≡ 124⋅124=15376 ≡ 212 mod 223

32: 93³²=93¹⁶⁺¹⁶=93¹⁶⋅93¹⁶ ≡ 212⋅212=44944 ≡ 121 mod 223

64: 93⁶⁴=93³²⁺³²=93³²⋅93³² ≡ 121⋅121=14641 ≡ 146 mod 223

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

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

62 = 32+16+8+4+2

240⁶²

= 240^32+16+8+4+2

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

≡ 290 ⋅ 381 ⋅ 116 ⋅ 193 ⋅ 70 mod 523
≡ 110490 ⋅ 116 ⋅ 193 ⋅ 70 mod 523 ≡ 137 ⋅ 116 ⋅ 193 ⋅ 70 mod 523
≡ 15892 ⋅ 193 ⋅ 70 mod 523 ≡ 202 ⋅ 193 ⋅ 70 mod 523
≡ 38986 ⋅ 70 mod 523 ≡ 284 ⋅ 70 mod 523
≡ 19880 mod 523 ≡ 6 mod 523

Es gilt also: 240⁶² ≡ 6 mod 523

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