Um längere Rechnungen zu vermeiden, rechnen wir:

(184 + 89) mod 9 ≡ (184 mod 9 + 89 mod 9) mod 9.

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

89 mod 9 ≡ 8 mod 9 kann man relativ leicht bestimmen, weil ja 89 = 90-1 = 9 ⋅ 10 -1 = 9 ⋅ 10 - 9 + 8.

Somit gilt:

(184 + 89) mod 9 ≡ (4 + 8) mod 9 ≡ 12 mod 9 ≡ 3 mod 9.

Um längere Rechnungen zu vermeiden, rechnen wir:

(48 ⋅ 66) mod 4 ≡ (48 mod 4 ⋅ 66 mod 4) mod 4.

48 mod 4 ≡ 0 mod 4 kann man relativ leicht bestimmen, weil ja 48 = 48 + 0 = 12 ⋅ 4 + 0 ist.

66 mod 4 ≡ 2 mod 4 kann man relativ leicht bestimmen, weil ja 66 = 64 + 2 = 16 ⋅ 4 + 2 ist.

Somit gilt:

(48 ⋅ 66) mod 4 ≡ (0 ⋅ 2) mod 4 ≡ 0 mod 4.

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

2: 174²=174¹⁺¹=174¹⋅174¹ ≡ 174⋅174=30276 ≡ 181 mod 463

4: 174⁴=174²⁺²=174²⋅174² ≡ 181⋅181=32761 ≡ 351 mod 463

8: 174⁸=174⁴⁺⁴=174⁴⋅174⁴ ≡ 351⋅351=123201 ≡ 43 mod 463

16: 174¹⁶=174⁸⁺⁸=174⁸⋅174⁸ ≡ 43⋅43=1849 ≡ 460 mod 463

32: 174³²=174¹⁶⁺¹⁶=174¹⁶⋅174¹⁶ ≡ 460⋅460=211600 ≡ 9 mod 463

64: 174⁶⁴=174³²⁺³²=174³²⋅174³² ≡ 9⋅9=81 ≡ 81 mod 463

128: 174¹²⁸=174⁶⁴⁺⁶⁴=174⁶⁴⋅174⁶⁴ ≡ 81⋅81=6561 ≡ 79 mod 463

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

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

227 = 128+64+32+2+1

714²²⁷

= 714^{128+64+32+2+1}

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

≡ 64 ⋅ 8 ⋅ 162 ⋅ 68 ⋅ 714 mod 937
≡ 512 ⋅ 162 ⋅ 68 ⋅ 714 mod 937
≡ 82944 ⋅ 68 ⋅ 714 mod 937 ≡ 488 ⋅ 68 ⋅ 714 mod 937
≡ 33184 ⋅ 714 mod 937 ≡ 389 ⋅ 714 mod 937
≡ 277746 mod 937 ≡ 394 mod 937

Es gilt also: 714²²⁷ ≡ 394 mod 937

Berechnung des größten gemeinsamen Teilers von 73 und 32

=>73	= 2⋅32 + 9
=>32	= 3⋅9 + 5
=>9	= 1⋅5 + 4
=>5	= 1⋅4 + 1
=>4	= 4⋅1 + 0

also gilt: ggt(73,32)=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= 5-1⋅4
4= 9-1⋅5	eingesetzt in die Zeile drüber:	1	= 1⋅5 -1⋅(9 -1⋅ 5) = 1⋅5 -1⋅9 +1⋅ 5) = -1⋅9 +2⋅ 5 (=1)
5= 32-3⋅9	eingesetzt in die Zeile drüber:	1	= -1⋅9 +2⋅(32 -3⋅ 9) = -1⋅9 +2⋅32 -6⋅ 9) = 2⋅32 -7⋅ 9 (=1)
9= 73-2⋅32	eingesetzt in die Zeile drüber:	1	= 2⋅32 -7⋅(73 -2⋅ 32) = 2⋅32 -7⋅73 +14⋅ 32) = -7⋅73 +16⋅ 32 (=1)

Es gilt also: ggt(73,32)=1 = -7⋅73 +16⋅32

oder wenn man -7⋅73 auf die linke Seite bringt:

1 +7⋅73 = +16⋅32

Es gilt also: 16⋅32 = 7⋅73 +1

Somit 16⋅32 = 1 mod 73

16 ist also das Inverse von 32 mod 73