Um längere Rechnungen zu vermeiden, rechnen wir:

(801 - 798) mod 4 ≡ (801 mod 4 - 798 mod 4) mod 4.

801 mod 4 ≡ 1 mod 4 kann man relativ leicht bestimmen, weil ja 801 = 800+1 = 4 ⋅ 200 +1.

798 mod 4 ≡ 2 mod 4 kann man relativ leicht bestimmen, weil ja 798 = 700+98 = 4 ⋅ 175 +98.

Somit gilt:

(801 - 798) mod 4 ≡ (1 - 2) mod 4 ≡ -1 mod 4 ≡ 3 mod 4.

Um längere Rechnungen zu vermeiden, rechnen wir:

(75 ⋅ 50) mod 5 ≡ (75 mod 5 ⋅ 50 mod 5) mod 5.

75 mod 5 ≡ 0 mod 5 kann man relativ leicht bestimmen, weil ja 75 = 75 + 0 = 15 ⋅ 5 + 0 ist.

50 mod 5 ≡ 0 mod 5 kann man relativ leicht bestimmen, weil ja 50 = 50 + 0 = 10 ⋅ 5 + 0 ist.

Somit gilt:

(75 ⋅ 50) mod 5 ≡ (0 ⋅ 0) mod 5 ≡ 0 mod 5.

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

2: 344²=344¹⁺¹=344¹⋅344¹ ≡ 344⋅344=118336 ≡ 248 mod 509

4: 344⁴=344²⁺²=344²⋅344² ≡ 248⋅248=61504 ≡ 424 mod 509

8: 344⁸=344⁴⁺⁴=344⁴⋅344⁴ ≡ 424⋅424=179776 ≡ 99 mod 509

16: 344¹⁶=344⁸⁺⁸=344⁸⋅344⁸ ≡ 99⋅99=9801 ≡ 130 mod 509

32: 344³²=344¹⁶⁺¹⁶=344¹⁶⋅344¹⁶ ≡ 130⋅130=16900 ≡ 103 mod 509

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

318¹²²

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

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

≡ 185 ⋅ 376 ⋅ 283 ⋅ 84 ⋅ 50 mod 521
≡ 69560 ⋅ 283 ⋅ 84 ⋅ 50 mod 521 ≡ 267 ⋅ 283 ⋅ 84 ⋅ 50 mod 521
≡ 75561 ⋅ 84 ⋅ 50 mod 521 ≡ 16 ⋅ 84 ⋅ 50 mod 521
≡ 1344 ⋅ 50 mod 521 ≡ 302 ⋅ 50 mod 521
≡ 15100 mod 521 ≡ 512 mod 521

Es gilt also: 318¹²² ≡ 512 mod 521

Berechnung des größten gemeinsamen Teilers von 73 und 25

=>73	= 2⋅25 + 23
=>25	= 1⋅23 + 2
=>23	= 11⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(73,25)=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= 23-11⋅2
2= 25-1⋅23	eingesetzt in die Zeile drüber:	1	= 1⋅23 -11⋅(25 -1⋅ 23) = 1⋅23 -11⋅25 +11⋅ 23) = -11⋅25 +12⋅ 23 (=1)
23= 73-2⋅25	eingesetzt in die Zeile drüber:	1	= -11⋅25 +12⋅(73 -2⋅ 25) = -11⋅25 +12⋅73 -24⋅ 25) = 12⋅73 -35⋅ 25 (=1)

Es gilt also: ggt(73,25)=1 = 12⋅73 -35⋅25

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

1 -12⋅73 = -35⋅25

-35⋅25 = -12⋅73 + 1 |+73⋅25

-35⋅25 + 73⋅25 = -12⋅73 + 73⋅25 + 1

(-35 + 73) ⋅ 25 = (-12 + 25) ⋅ 73 + 1

38⋅25 = 13⋅73 + 1

Es gilt also: 38⋅25 = 13⋅73 +1

Somit 38⋅25 = 1 mod 73

38 ist also das Inverse von 25 mod 73