Um längere Rechnungen zu vermeiden, rechnen wir:

(12003 + 119) mod 6 ≡ (12003 mod 6 + 119 mod 6) mod 6.

12003 mod 6 ≡ 3 mod 6 kann man relativ leicht bestimmen, weil ja 12003 = 12000+3 = 6 ⋅ 2000 +3.

119 mod 6 ≡ 5 mod 6 kann man relativ leicht bestimmen, weil ja 119 = 120-1 = 6 ⋅ 20 -1 = 6 ⋅ 20 - 6 + 5.

Somit gilt:

(12003 + 119) mod 6 ≡ (3 + 5) mod 6 ≡ 8 mod 6 ≡ 2 mod 6.

Um längere Rechnungen zu vermeiden, rechnen wir:

(74 ⋅ 53) mod 6 ≡ (74 mod 6 ⋅ 53 mod 6) mod 6.

74 mod 6 ≡ 2 mod 6 kann man relativ leicht bestimmen, weil ja 74 = 72 + 2 = 12 ⋅ 6 + 2 ist.

53 mod 6 ≡ 5 mod 6 kann man relativ leicht bestimmen, weil ja 53 = 48 + 5 = 8 ⋅ 6 + 5 ist.

Somit gilt:

(74 ⋅ 53) mod 6 ≡ (2 ⋅ 5) mod 6 ≡ 10 mod 6 ≡ 4 mod 6.

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

2: 534²=534¹⁺¹=534¹⋅534¹ ≡ 534⋅534=285156 ≡ 169 mod 547

4: 534⁴=534²⁺²=534²⋅534² ≡ 169⋅169=28561 ≡ 117 mod 547

8: 534⁸=534⁴⁺⁴=534⁴⋅534⁴ ≡ 117⋅117=13689 ≡ 14 mod 547

16: 534¹⁶=534⁸⁺⁸=534⁸⋅534⁸ ≡ 14⋅14=196 ≡ 196 mod 547

32: 534³²=534¹⁶⁺¹⁶=534¹⁶⋅534¹⁶ ≡ 196⋅196=38416 ≡ 126 mod 547

64: 534⁶⁴=534³²⁺³²=534³²⋅534³² ≡ 126⋅126=15876 ≡ 13 mod 547

128: 534¹²⁸=534⁶⁴⁺⁶⁴=534⁶⁴⋅534⁶⁴ ≡ 13⋅13=169 ≡ 169 mod 547

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

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

166 = 128+32+4+2

135¹⁶⁶

= 135^128+32+4+2

= 135¹²⁸⋅135³²⋅135⁴⋅135²

≡ 267 ⋅ 237 ⋅ 137 ⋅ 187 mod 311
≡ 63279 ⋅ 137 ⋅ 187 mod 311 ≡ 146 ⋅ 137 ⋅ 187 mod 311
≡ 20002 ⋅ 187 mod 311 ≡ 98 ⋅ 187 mod 311
≡ 18326 mod 311 ≡ 288 mod 311

Es gilt also: 135¹⁶⁶ ≡ 288 mod 311

Berechnung des größten gemeinsamen Teilers von 97 und 52

=>97	= 1⋅52 + 45
=>52	= 1⋅45 + 7
=>45	= 6⋅7 + 3
=>7	= 2⋅3 + 1
=>3	= 3⋅1 + 0

also gilt: ggt(97,52)=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-2⋅3
3= 45-6⋅7	eingesetzt in die Zeile drüber:	1	= 1⋅7 -2⋅(45 -6⋅ 7) = 1⋅7 -2⋅45 +12⋅ 7) = -2⋅45 +13⋅ 7 (=1)
7= 52-1⋅45	eingesetzt in die Zeile drüber:	1	= -2⋅45 +13⋅(52 -1⋅ 45) = -2⋅45 +13⋅52 -13⋅ 45) = 13⋅52 -15⋅ 45 (=1)
45= 97-1⋅52	eingesetzt in die Zeile drüber:	1	= 13⋅52 -15⋅(97 -1⋅ 52) = 13⋅52 -15⋅97 +15⋅ 52) = -15⋅97 +28⋅ 52 (=1)

Es gilt also: ggt(97,52)=1 = -15⋅97 +28⋅52

oder wenn man -15⋅97 auf die linke Seite bringt:

1 +15⋅97 = +28⋅52

Es gilt also: 28⋅52 = 15⋅97 +1

Somit 28⋅52 = 1 mod 97

28 ist also das Inverse von 52 mod 97