Um längere Rechnungen zu vermeiden, rechnen wir:

(2398 + 1800) mod 6 ≡ (2398 mod 6 + 1800 mod 6) mod 6.

2398 mod 6 ≡ 4 mod 6 kann man relativ leicht bestimmen, weil ja 2398 = 2400-2 = 6 ⋅ 400 -2 = 6 ⋅ 400 - 6 + 4.

1800 mod 6 ≡ 0 mod 6 kann man relativ leicht bestimmen, weil ja 1800 = 1800+0 = 6 ⋅ 300 +0.

Somit gilt:

(2398 + 1800) mod 6 ≡ (4 + 0) mod 6 ≡ 4 mod 6.

Um längere Rechnungen zu vermeiden, rechnen wir:

(75 ⋅ 53) mod 7 ≡ (75 mod 7 ⋅ 53 mod 7) mod 7.

75 mod 7 ≡ 5 mod 7 kann man relativ leicht bestimmen, weil ja 75 = 70 + 5 = 10 ⋅ 7 + 5 ist.

53 mod 7 ≡ 4 mod 7 kann man relativ leicht bestimmen, weil ja 53 = 49 + 4 = 7 ⋅ 7 + 4 ist.

Somit gilt:

(75 ⋅ 53) mod 7 ≡ (5 ⋅ 4) mod 7 ≡ 20 mod 7 ≡ 6 mod 7.

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

2: 511²=511¹⁺¹=511¹⋅511¹ ≡ 511⋅511=261121 ≡ 518 mod 631

4: 511⁴=511²⁺²=511²⋅511² ≡ 518⋅518=268324 ≡ 149 mod 631

8: 511⁸=511⁴⁺⁴=511⁴⋅511⁴ ≡ 149⋅149=22201 ≡ 116 mod 631

16: 511¹⁶=511⁸⁺⁸=511⁸⋅511⁸ ≡ 116⋅116=13456 ≡ 205 mod 631

32: 511³²=511¹⁶⁺¹⁶=511¹⁶⋅511¹⁶ ≡ 205⋅205=42025 ≡ 379 mod 631

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

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

121 = 64+32+16+8+1

303¹²¹

= 303^64+32+16+8+1

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

≡ 256 ⋅ 16 ⋅ 345 ⋅ 77 ⋅ 303 mod 349
≡ 4096 ⋅ 345 ⋅ 77 ⋅ 303 mod 349 ≡ 257 ⋅ 345 ⋅ 77 ⋅ 303 mod 349
≡ 88665 ⋅ 77 ⋅ 303 mod 349 ≡ 19 ⋅ 77 ⋅ 303 mod 349
≡ 1463 ⋅ 303 mod 349 ≡ 67 ⋅ 303 mod 349
≡ 20301 mod 349 ≡ 59 mod 349

Es gilt also: 303¹²¹ ≡ 59 mod 349

Berechnung des größten gemeinsamen Teilers von 83 und 31

=>83	= 2⋅31 + 21
=>31	= 1⋅21 + 10
=>21	= 2⋅10 + 1
=>10	= 10⋅1 + 0

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

Es gilt also: ggt(83,31)=1 = 3⋅83 -8⋅31

oder wenn man 3⋅83 auf die linke Seite bringt:

1 -3⋅83 = -8⋅31

-8⋅31 = -3⋅83 + 1 |+83⋅31

-8⋅31 + 83⋅31 = -3⋅83 + 83⋅31 + 1

(-8 + 83) ⋅ 31 = (-3 + 31) ⋅ 83 + 1

75⋅31 = 28⋅83 + 1

Es gilt also: 75⋅31 = 28⋅83 +1

Somit 75⋅31 = 1 mod 83

75 ist also das Inverse von 31 mod 83