Um längere Rechnungen zu vermeiden, rechnen wir:

(36007 + 368) mod 9 ≡ (36007 mod 9 + 368 mod 9) mod 9.

36007 mod 9 ≡ 7 mod 9 kann man relativ leicht bestimmen, weil ja 36007 = 36000+7 = 9 ⋅ 4000 +7.

368 mod 9 ≡ 8 mod 9 kann man relativ leicht bestimmen, weil ja 368 = 360+8 = 9 ⋅ 40 +8.

Somit gilt:

(36007 + 368) mod 9 ≡ (7 + 8) mod 9 ≡ 15 mod 9 ≡ 6 mod 9.

Um längere Rechnungen zu vermeiden, rechnen wir:

(65 ⋅ 44) mod 3 ≡ (65 mod 3 ⋅ 44 mod 3) mod 3.

65 mod 3 ≡ 2 mod 3 kann man relativ leicht bestimmen, weil ja 65 = 63 + 2 = 21 ⋅ 3 + 2 ist.

44 mod 3 ≡ 2 mod 3 kann man relativ leicht bestimmen, weil ja 44 = 42 + 2 = 14 ⋅ 3 + 2 ist.

Somit gilt:

(65 ⋅ 44) mod 3 ≡ (2 ⋅ 2) mod 3 ≡ 4 mod 3 ≡ 1 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: 168¹=168

2: 168²=168¹⁺¹=168¹⋅168¹ ≡ 168⋅168=28224 ≡ 40 mod 271

4: 168⁴=168²⁺²=168²⋅168² ≡ 40⋅40=1600 ≡ 245 mod 271

8: 168⁸=168⁴⁺⁴=168⁴⋅168⁴ ≡ 245⋅245=60025 ≡ 134 mod 271

16: 168¹⁶=168⁸⁺⁸=168⁸⋅168⁸ ≡ 134⋅134=17956 ≡ 70 mod 271

32: 168³²=168¹⁶⁺¹⁶=168¹⁶⋅168¹⁶ ≡ 70⋅70=4900 ≡ 22 mod 271

64: 168⁶⁴=168³²⁺³²=168³²⋅168³² ≡ 22⋅22=484 ≡ 213 mod 271

128: 168¹²⁸=168⁶⁴⁺⁶⁴=168⁶⁴⋅168⁶⁴ ≡ 213⋅213=45369 ≡ 112 mod 271

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

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

170 = 128+32+8+2

421¹⁷⁰

= 421^128+32+8+2

= 421¹²⁸⋅421³²⋅421⁸⋅421²

≡ 13 ⋅ 196 ⋅ 117 ⋅ 13 mod 547
≡ 2548 ⋅ 117 ⋅ 13 mod 547 ≡ 360 ⋅ 117 ⋅ 13 mod 547
≡ 42120 ⋅ 13 mod 547 ≡ 1 ⋅ 13 mod 547
≡ 13 mod 547

Es gilt also: 421¹⁷⁰ ≡ 13 mod 547

Berechnung des größten gemeinsamen Teilers von 53 und 20

=>53	= 2⋅20 + 13
=>20	= 1⋅13 + 7
=>13	= 1⋅7 + 6
=>7	= 1⋅6 + 1
=>6	= 6⋅1 + 0

also gilt: ggt(53,20)=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= 7-1⋅6
6= 13-1⋅7	eingesetzt in die Zeile drüber:	1	= 1⋅7 -1⋅(13 -1⋅ 7) = 1⋅7 -1⋅13 +1⋅ 7) = -1⋅13 +2⋅ 7 (=1)
7= 20-1⋅13	eingesetzt in die Zeile drüber:	1	= -1⋅13 +2⋅(20 -1⋅ 13) = -1⋅13 +2⋅20 -2⋅ 13) = 2⋅20 -3⋅ 13 (=1)
13= 53-2⋅20	eingesetzt in die Zeile drüber:	1	= 2⋅20 -3⋅(53 -2⋅ 20) = 2⋅20 -3⋅53 +6⋅ 20) = -3⋅53 +8⋅ 20 (=1)

Es gilt also: ggt(53,20)=1 = -3⋅53 +8⋅20

oder wenn man -3⋅53 auf die linke Seite bringt:

1 +3⋅53 = +8⋅20

Es gilt also: 8⋅20 = 3⋅53 +1

Somit 8⋅20 = 1 mod 53

8 ist also das Inverse von 20 mod 53