Um längere Rechnungen zu vermeiden, rechnen wir:

(12001 + 8003) mod 4 ≡ (12001 mod 4 + 8003 mod 4) mod 4.

12001 mod 4 ≡ 1 mod 4 kann man relativ leicht bestimmen, weil ja 12001 = 12000+1 = 4 ⋅ 3000 +1.

8003 mod 4 ≡ 3 mod 4 kann man relativ leicht bestimmen, weil ja 8003 = 8000+3 = 4 ⋅ 2000 +3.

Somit gilt:

(12001 + 8003) mod 4 ≡ (1 + 3) mod 4 ≡ 4 mod 4 ≡ 0 mod 4.

Um längere Rechnungen zu vermeiden, rechnen wir:

(23 ⋅ 95) mod 3 ≡ (23 mod 3 ⋅ 95 mod 3) mod 3.

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

95 mod 3 ≡ 2 mod 3 kann man relativ leicht bestimmen, weil ja 95 = 93 + 2 = 31 ⋅ 3 + 2 ist.

Somit gilt:

(23 ⋅ 95) mod 3 ≡ (2 ⋅ 2) mod 3 ≡ 4 mod 3 ≡ 1 mod 3.

Die 8 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: 530¹=530

2: 530²=530¹⁺¹=530¹⋅530¹ ≡ 530⋅530=280900 ≡ 215 mod 769

4: 530⁴=530²⁺²=530²⋅530² ≡ 215⋅215=46225 ≡ 85 mod 769

8: 530⁸=530⁴⁺⁴=530⁴⋅530⁴ ≡ 85⋅85=7225 ≡ 304 mod 769

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

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

253 = 128+64+32+16+8+4+1

137²⁵³

= 137^{128+64+32+16+8+4+1}

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

≡ 235 ⋅ 70 ⋅ 267 ⋅ 189 ⋅ 237 ⋅ 63 ⋅ 137 mod 311
≡ 16450 ⋅ 267 ⋅ 189 ⋅ 237 ⋅ 63 ⋅ 137 mod 311 ≡ 278 ⋅ 267 ⋅ 189 ⋅ 237 ⋅ 63 ⋅ 137 mod 311
≡ 74226 ⋅ 189 ⋅ 237 ⋅ 63 ⋅ 137 mod 311 ≡ 208 ⋅ 189 ⋅ 237 ⋅ 63 ⋅ 137 mod 311
≡ 39312 ⋅ 237 ⋅ 63 ⋅ 137 mod 311 ≡ 126 ⋅ 237 ⋅ 63 ⋅ 137 mod 311
≡ 29862 ⋅ 63 ⋅ 137 mod 311 ≡ 6 ⋅ 63 ⋅ 137 mod 311
≡ 378 ⋅ 137 mod 311 ≡ 67 ⋅ 137 mod 311
≡ 9179 mod 311 ≡ 160 mod 311

Es gilt also: 137²⁵³ ≡ 160 mod 311

Berechnung des größten gemeinsamen Teilers von 71 und 65

=>71	= 1⋅65 + 6
=>65	= 10⋅6 + 5
=>6	= 1⋅5 + 1
=>5	= 5⋅1 + 0

also gilt: ggt(71,65)=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= 6-1⋅5
5= 65-10⋅6	eingesetzt in die Zeile drüber:	1	= 1⋅6 -1⋅(65 -10⋅ 6) = 1⋅6 -1⋅65 +10⋅ 6) = -1⋅65 +11⋅ 6 (=1)
6= 71-1⋅65	eingesetzt in die Zeile drüber:	1	= -1⋅65 +11⋅(71 -1⋅ 65) = -1⋅65 +11⋅71 -11⋅ 65) = 11⋅71 -12⋅ 65 (=1)

Es gilt also: ggt(71,65)=1 = 11⋅71 -12⋅65

oder wenn man 11⋅71 auf die linke Seite bringt:

1 -11⋅71 = -12⋅65

-12⋅65 = -11⋅71 + 1 |+71⋅65

-12⋅65 + 71⋅65 = -11⋅71 + 71⋅65 + 1

(-12 + 71) ⋅ 65 = (-11 + 65) ⋅ 71 + 1

59⋅65 = 54⋅71 + 1

Es gilt also: 59⋅65 = 54⋅71 +1

Somit 59⋅65 = 1 mod 71

59 ist also das Inverse von 65 mod 71