Um längere Rechnungen zu vermeiden, rechnen wir:

(598 + 1195) mod 6 ≡ (598 mod 6 + 1195 mod 6) mod 6.

598 mod 6 ≡ 4 mod 6 kann man relativ leicht bestimmen, weil ja 598 = 600-2 = 6 ⋅ 100 -2 = 6 ⋅ 100 - 6 + 4.

1195 mod 6 ≡ 1 mod 6 kann man relativ leicht bestimmen, weil ja 1195 = 1200-5 = 6 ⋅ 200 -5 = 6 ⋅ 200 - 6 + 1.

Somit gilt:

(598 + 1195) mod 6 ≡ (4 + 1) mod 6 ≡ 5 mod 6.

Um längere Rechnungen zu vermeiden, rechnen wir:

(21 ⋅ 28) mod 5 ≡ (21 mod 5 ⋅ 28 mod 5) mod 5.

21 mod 5 ≡ 1 mod 5 kann man relativ leicht bestimmen, weil ja 21 = 20 + 1 = 4 ⋅ 5 + 1 ist.

28 mod 5 ≡ 3 mod 5 kann man relativ leicht bestimmen, weil ja 28 = 25 + 3 = 5 ⋅ 5 + 3 ist.

Somit gilt:

(21 ⋅ 28) mod 5 ≡ (1 ⋅ 3) mod 5 ≡ 3 mod 5.

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

2: 326²=326¹⁺¹=326¹⋅326¹ ≡ 326⋅326=106276 ≡ 269 mod 419

4: 326⁴=326²⁺²=326²⋅326² ≡ 269⋅269=72361 ≡ 293 mod 419

8: 326⁸=326⁴⁺⁴=326⁴⋅326⁴ ≡ 293⋅293=85849 ≡ 373 mod 419

16: 326¹⁶=326⁸⁺⁸=326⁸⋅326⁸ ≡ 373⋅373=139129 ≡ 21 mod 419

32: 326³²=326¹⁶⁺¹⁶=326¹⁶⋅326¹⁶ ≡ 21⋅21=441 ≡ 22 mod 419

64: 326⁶⁴=326³²⁺³²=326³²⋅326³² ≡ 22⋅22=484 ≡ 65 mod 419

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

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

235 = 128+64+32+8+2+1

498²³⁵

= 498^{128+64+32+8+2+1}

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

≡ 562 ⋅ 776 ⋅ 149 ⋅ 228 ⋅ 331 ⋅ 498 mod 857
≡ 436112 ⋅ 149 ⋅ 228 ⋅ 331 ⋅ 498 mod 857 ≡ 756 ⋅ 149 ⋅ 228 ⋅ 331 ⋅ 498 mod 857
≡ 112644 ⋅ 228 ⋅ 331 ⋅ 498 mod 857 ≡ 377 ⋅ 228 ⋅ 331 ⋅ 498 mod 857
≡ 85956 ⋅ 331 ⋅ 498 mod 857 ≡ 256 ⋅ 331 ⋅ 498 mod 857
≡ 84736 ⋅ 498 mod 857 ≡ 750 ⋅ 498 mod 857
≡ 373500 mod 857 ≡ 705 mod 857

Es gilt also: 498²³⁵ ≡ 705 mod 857

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

=>71	= 1⋅53 + 18
=>53	= 2⋅18 + 17
=>18	= 1⋅17 + 1
=>17	= 17⋅1 + 0

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

Es gilt also: ggt(71,53)=1 = 3⋅71 -4⋅53

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

1 -3⋅71 = -4⋅53

-4⋅53 = -3⋅71 + 1 |+71⋅53

-4⋅53 + 71⋅53 = -3⋅71 + 71⋅53 + 1

(-4 + 71) ⋅ 53 = (-3 + 53) ⋅ 71 + 1

67⋅53 = 50⋅71 + 1

Es gilt also: 67⋅53 = 50⋅71 +1

Somit 67⋅53 = 1 mod 71

67 ist also das Inverse von 53 mod 71