Um längere Rechnungen zu vermeiden, rechnen wir:

(150 + 8999) mod 3 ≡ (150 mod 3 + 8999 mod 3) mod 3.

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

8999 mod 3 ≡ 2 mod 3 kann man relativ leicht bestimmen, weil ja 8999 = 9000-1 = 3 ⋅ 3000 -1 = 3 ⋅ 3000 - 3 + 2.

Somit gilt:

(150 + 8999) mod 3 ≡ (0 + 2) mod 3 ≡ 2 mod 3.

Um längere Rechnungen zu vermeiden, rechnen wir:

(31 ⋅ 70) mod 11 ≡ (31 mod 11 ⋅ 70 mod 11) mod 11.

31 mod 11 ≡ 9 mod 11 kann man relativ leicht bestimmen, weil ja 31 = 22 + 9 = 2 ⋅ 11 + 9 ist.

70 mod 11 ≡ 4 mod 11 kann man relativ leicht bestimmen, weil ja 70 = 66 + 4 = 6 ⋅ 11 + 4 ist.

Somit gilt:

(31 ⋅ 70) mod 11 ≡ (9 ⋅ 4) mod 11 ≡ 36 mod 11 ≡ 3 mod 11.

Die 32 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: 164¹=164

2: 164²=164¹⁺¹=164¹⋅164¹ ≡ 164⋅164=26896 ≡ 103 mod 229

4: 164⁴=164²⁺²=164²⋅164² ≡ 103⋅103=10609 ≡ 75 mod 229

8: 164⁸=164⁴⁺⁴=164⁴⋅164⁴ ≡ 75⋅75=5625 ≡ 129 mod 229

16: 164¹⁶=164⁸⁺⁸=164⁸⋅164⁸ ≡ 129⋅129=16641 ≡ 153 mod 229

32: 164³²=164¹⁶⁺¹⁶=164¹⁶⋅164¹⁶ ≡ 153⋅153=23409 ≡ 51 mod 229

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

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

151 = 128+16+4+2+1

223¹⁵¹

= 223^128+16+4+2+1

= 223¹²⁸⋅223¹⁶⋅223⁴⋅223²⋅223¹

≡ 211 ⋅ 30 ⋅ 264 ⋅ 146 ⋅ 223 mod 277
≡ 6330 ⋅ 264 ⋅ 146 ⋅ 223 mod 277 ≡ 236 ⋅ 264 ⋅ 146 ⋅ 223 mod 277
≡ 62304 ⋅ 146 ⋅ 223 mod 277 ≡ 256 ⋅ 146 ⋅ 223 mod 277
≡ 37376 ⋅ 223 mod 277 ≡ 258 ⋅ 223 mod 277
≡ 57534 mod 277 ≡ 195 mod 277

Es gilt also: 223¹⁵¹ ≡ 195 mod 277

Berechnung des größten gemeinsamen Teilers von 67 und 36

=>67	= 1⋅36 + 31
=>36	= 1⋅31 + 5
=>31	= 6⋅5 + 1
=>5	= 5⋅1 + 0

also gilt: ggt(67,36)=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= 31-6⋅5
5= 36-1⋅31	eingesetzt in die Zeile drüber:	1	= 1⋅31 -6⋅(36 -1⋅ 31) = 1⋅31 -6⋅36 +6⋅ 31) = -6⋅36 +7⋅ 31 (=1)
31= 67-1⋅36	eingesetzt in die Zeile drüber:	1	= -6⋅36 +7⋅(67 -1⋅ 36) = -6⋅36 +7⋅67 -7⋅ 36) = 7⋅67 -13⋅ 36 (=1)

Es gilt also: ggt(67,36)=1 = 7⋅67 -13⋅36

oder wenn man 7⋅67 auf die linke Seite bringt:

1 -7⋅67 = -13⋅36

-13⋅36 = -7⋅67 + 1 |+67⋅36

-13⋅36 + 67⋅36 = -7⋅67 + 67⋅36 + 1

(-13 + 67) ⋅ 36 = (-7 + 36) ⋅ 67 + 1

54⋅36 = 29⋅67 + 1

Es gilt also: 54⋅36 = 29⋅67 +1

Somit 54⋅36 = 1 mod 67

54 ist also das Inverse von 36 mod 67