Um längere Rechnungen zu vermeiden, rechnen wir:

(4998 + 2500) mod 5 ≡ (4998 mod 5 + 2500 mod 5) mod 5.

4998 mod 5 ≡ 3 mod 5 kann man relativ leicht bestimmen, weil ja 4998 = 4000+998 = 5 ⋅ 800 +998.

2500 mod 5 ≡ 0 mod 5 kann man relativ leicht bestimmen, weil ja 2500 = 2500+0 = 5 ⋅ 500 +0.

Somit gilt:

(4998 + 2500) mod 5 ≡ (3 + 0) mod 5 ≡ 3 mod 5.

Um längere Rechnungen zu vermeiden, rechnen wir:

(24 ⋅ 28) mod 4 ≡ (24 mod 4 ⋅ 28 mod 4) mod 4.

24 mod 4 ≡ 0 mod 4 kann man relativ leicht bestimmen, weil ja 24 = 24 + 0 = 6 ⋅ 4 + 0 ist.

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

Somit gilt:

(24 ⋅ 28) mod 4 ≡ (0 ⋅ 0) mod 4 ≡ 0 mod 4.

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

2: 458²=458¹⁺¹=458¹⋅458¹ ≡ 458⋅458=209764 ≡ 435 mod 593

4: 458⁴=458²⁺²=458²⋅458² ≡ 435⋅435=189225 ≡ 58 mod 593

8: 458⁸=458⁴⁺⁴=458⁴⋅458⁴ ≡ 58⋅58=3364 ≡ 399 mod 593

16: 458¹⁶=458⁸⁺⁸=458⁸⋅458⁸ ≡ 399⋅399=159201 ≡ 277 mod 593

32: 458³²=458¹⁶⁺¹⁶=458¹⁶⋅458¹⁶ ≡ 277⋅277=76729 ≡ 232 mod 593

64: 458⁶⁴=458³²⁺³²=458³²⋅458³² ≡ 232⋅232=53824 ≡ 454 mod 593

128: 458¹²⁸=458⁶⁴⁺⁶⁴=458⁶⁴⋅458⁶⁴ ≡ 454⋅454=206116 ≡ 345 mod 593

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

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

122 = 64+32+16+8+2

666¹²²

= 666^64+32+16+8+2

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

≡ 592 ⋅ 537 ⋅ 168 ⋅ 640 ⋅ 564 mod 839
≡ 317904 ⋅ 168 ⋅ 640 ⋅ 564 mod 839 ≡ 762 ⋅ 168 ⋅ 640 ⋅ 564 mod 839
≡ 128016 ⋅ 640 ⋅ 564 mod 839 ≡ 488 ⋅ 640 ⋅ 564 mod 839
≡ 312320 ⋅ 564 mod 839 ≡ 212 ⋅ 564 mod 839
≡ 119568 mod 839 ≡ 430 mod 839

Es gilt also: 666¹²² ≡ 430 mod 839

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

=>71	= 1⋅37 + 34
=>37	= 1⋅34 + 3
=>34	= 11⋅3 + 1
=>3	= 3⋅1 + 0

also gilt: ggt(71,37)=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= 34-11⋅3
3= 37-1⋅34	eingesetzt in die Zeile drüber:	1	= 1⋅34 -11⋅(37 -1⋅ 34) = 1⋅34 -11⋅37 +11⋅ 34) = -11⋅37 +12⋅ 34 (=1)
34= 71-1⋅37	eingesetzt in die Zeile drüber:	1	= -11⋅37 +12⋅(71 -1⋅ 37) = -11⋅37 +12⋅71 -12⋅ 37) = 12⋅71 -23⋅ 37 (=1)

Es gilt also: ggt(71,37)=1 = 12⋅71 -23⋅37

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

1 -12⋅71 = -23⋅37

-23⋅37 = -12⋅71 + 1 |+71⋅37

-23⋅37 + 71⋅37 = -12⋅71 + 71⋅37 + 1

(-23 + 71) ⋅ 37 = (-12 + 37) ⋅ 71 + 1

48⋅37 = 25⋅71 + 1

Es gilt also: 48⋅37 = 25⋅71 +1

Somit 48⋅37 = 1 mod 71

48 ist also das Inverse von 37 mod 71