Um längere Rechnungen zu vermeiden, rechnen wir:

(120 + 151) mod 3 ≡ (120 mod 3 + 151 mod 3) mod 3.

120 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 120 = 120+0 = 3 ⋅ 40 +0.

151 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 151 = 150+1 = 3 ⋅ 50 +1.

Somit gilt:

(120 + 151) mod 3 ≡ (0 + 1) mod 3 ≡ 1 mod 3.

Um längere Rechnungen zu vermeiden, rechnen wir:

(38 ⋅ 76) mod 3 ≡ (38 mod 3 ⋅ 76 mod 3) mod 3.

38 mod 3 ≡ 2 mod 3 kann man relativ leicht bestimmen, weil ja 38 = 36 + 2 = 12 ⋅ 3 + 2 ist.

76 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 76 = 75 + 1 = 25 ⋅ 3 + 1 ist.

Somit gilt:

(38 ⋅ 76) mod 3 ≡ (2 ⋅ 1) mod 3 ≡ 2 mod 3.

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

2: 317²=317¹⁺¹=317¹⋅317¹ ≡ 317⋅317=100489 ≡ 422 mod 827

4: 317⁴=317²⁺²=317²⋅317² ≡ 422⋅422=178084 ≡ 279 mod 827

8: 317⁸=317⁴⁺⁴=317⁴⋅317⁴ ≡ 279⋅279=77841 ≡ 103 mod 827

16: 317¹⁶=317⁸⁺⁸=317⁸⋅317⁸ ≡ 103⋅103=10609 ≡ 685 mod 827

32: 317³²=317¹⁶⁺¹⁶=317¹⁶⋅317¹⁶ ≡ 685⋅685=469225 ≡ 316 mod 827

64: 317⁶⁴=317³²⁺³²=317³²⋅317³² ≡ 316⋅316=99856 ≡ 616 mod 827

128: 317¹²⁸=317⁶⁴⁺⁶⁴=317⁶⁴⋅317⁶⁴ ≡ 616⋅616=379456 ≡ 690 mod 827

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

211²³¹

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

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

≡ 143 ⋅ 139 ⋅ 94 ⋅ 220 ⋅ 144 ⋅ 211 mod 223
≡ 19877 ⋅ 94 ⋅ 220 ⋅ 144 ⋅ 211 mod 223 ≡ 30 ⋅ 94 ⋅ 220 ⋅ 144 ⋅ 211 mod 223
≡ 2820 ⋅ 220 ⋅ 144 ⋅ 211 mod 223 ≡ 144 ⋅ 220 ⋅ 144 ⋅ 211 mod 223
≡ 31680 ⋅ 144 ⋅ 211 mod 223 ≡ 14 ⋅ 144 ⋅ 211 mod 223
≡ 2016 ⋅ 211 mod 223 ≡ 9 ⋅ 211 mod 223
≡ 1899 mod 223 ≡ 115 mod 223

Es gilt also: 211²³¹ ≡ 115 mod 223

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

=>73	= 2⋅29 + 15
=>29	= 1⋅15 + 14
=>15	= 1⋅14 + 1
=>14	= 14⋅1 + 0

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

Es gilt also: ggt(73,29)=1 = 2⋅73 -5⋅29

oder wenn man 2⋅73 auf die linke Seite bringt:

1 -2⋅73 = -5⋅29

-5⋅29 = -2⋅73 + 1 |+73⋅29

-5⋅29 + 73⋅29 = -2⋅73 + 73⋅29 + 1

(-5 + 73) ⋅ 29 = (-2 + 29) ⋅ 73 + 1

68⋅29 = 27⋅73 + 1

Es gilt also: 68⋅29 = 27⋅73 +1

Somit 68⋅29 = 1 mod 73

68 ist also das Inverse von 29 mod 73