Um längere Rechnungen zu vermeiden, rechnen wir:

(5995 + 2397) mod 6 ≡ (5995 mod 6 + 2397 mod 6) mod 6.

5995 mod 6 ≡ 1 mod 6 kann man relativ leicht bestimmen, weil ja 5995 = 6000-5 = 6 ⋅ 1000 -5 = 6 ⋅ 1000 - 6 + 1.

2397 mod 6 ≡ 3 mod 6 kann man relativ leicht bestimmen, weil ja 2397 = 2400-3 = 6 ⋅ 400 -3 = 6 ⋅ 400 - 6 + 3.

Somit gilt:

(5995 + 2397) mod 6 ≡ (1 + 3) mod 6 ≡ 4 mod 6.

Um längere Rechnungen zu vermeiden, rechnen wir:

(69 ⋅ 31) mod 4 ≡ (69 mod 4 ⋅ 31 mod 4) mod 4.

69 mod 4 ≡ 1 mod 4 kann man relativ leicht bestimmen, weil ja 69 = 68 + 1 = 17 ⋅ 4 + 1 ist.

31 mod 4 ≡ 3 mod 4 kann man relativ leicht bestimmen, weil ja 31 = 28 + 3 = 7 ⋅ 4 + 3 ist.

Somit gilt:

(69 ⋅ 31) mod 4 ≡ (1 ⋅ 3) mod 4 ≡ 3 mod 4.

Die 64 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: 824¹=824

2: 824²=824¹⁺¹=824¹⋅824¹ ≡ 824⋅824=678976 ≡ 832 mod 883

4: 824⁴=824²⁺²=824²⋅824² ≡ 832⋅832=692224 ≡ 835 mod 883

8: 824⁸=824⁴⁺⁴=824⁴⋅824⁴ ≡ 835⋅835=697225 ≡ 538 mod 883

16: 824¹⁶=824⁸⁺⁸=824⁸⋅824⁸ ≡ 538⋅538=289444 ≡ 703 mod 883

32: 824³²=824¹⁶⁺¹⁶=824¹⁶⋅824¹⁶ ≡ 703⋅703=494209 ≡ 612 mod 883

64: 824⁶⁴=824³²⁺³²=824³²⋅824³² ≡ 612⋅612=374544 ≡ 152 mod 883

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

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

249 = 128+64+32+16+8+1

200²⁴⁹

= 200^{128+64+32+16+8+1}

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

≡ 1 ⋅ 256 ⋅ 16 ⋅ 253 ⋅ 32 ⋅ 200 mod 257
≡ 256 ⋅ 16 ⋅ 253 ⋅ 32 ⋅ 200 mod 257
≡ 4096 ⋅ 253 ⋅ 32 ⋅ 200 mod 257 ≡ 241 ⋅ 253 ⋅ 32 ⋅ 200 mod 257
≡ 60973 ⋅ 32 ⋅ 200 mod 257 ≡ 64 ⋅ 32 ⋅ 200 mod 257
≡ 2048 ⋅ 200 mod 257 ≡ 249 ⋅ 200 mod 257
≡ 49800 mod 257 ≡ 199 mod 257

Es gilt also: 200²⁴⁹ ≡ 199 mod 257

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

=>53	= 1⋅35 + 18
=>35	= 1⋅18 + 17
=>18	= 1⋅17 + 1
=>17	= 17⋅1 + 0

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

Es gilt also: ggt(53,35)=1 = 2⋅53 -3⋅35

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

1 -2⋅53 = -3⋅35

-3⋅35 = -2⋅53 + 1 |+53⋅35

-3⋅35 + 53⋅35 = -2⋅53 + 53⋅35 + 1

(-3 + 53) ⋅ 35 = (-2 + 35) ⋅ 53 + 1

50⋅35 = 33⋅53 + 1

Es gilt also: 50⋅35 = 33⋅53 +1

Somit 50⋅35 = 1 mod 53

50 ist also das Inverse von 35 mod 53