Um längere Rechnungen zu vermeiden, rechnen wir:

(1398 + 70) mod 7 ≡ (1398 mod 7 + 70 mod 7) mod 7.

1398 mod 7 ≡ 5 mod 7 kann man relativ leicht bestimmen, weil ja 1398 = 1400-2 = 7 ⋅ 200 -2 = 7 ⋅ 200 - 7 + 5.

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

Somit gilt:

(1398 + 70) mod 7 ≡ (5 + 0) mod 7 ≡ 5 mod 7.

Um längere Rechnungen zu vermeiden, rechnen wir:

(79 ⋅ 77) mod 11 ≡ (79 mod 11 ⋅ 77 mod 11) mod 11.

79 mod 11 ≡ 2 mod 11 kann man relativ leicht bestimmen, weil ja 79 = 77 + 2 = 7 ⋅ 11 + 2 ist.

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

Somit gilt:

(79 ⋅ 77) mod 11 ≡ (2 ⋅ 0) mod 11 ≡ 0 mod 11.

Die 16 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: 519¹=519

2: 519²=519¹⁺¹=519¹⋅519¹ ≡ 519⋅519=269361 ≡ 113 mod 601

4: 519⁴=519²⁺²=519²⋅519² ≡ 113⋅113=12769 ≡ 148 mod 601

8: 519⁸=519⁴⁺⁴=519⁴⋅519⁴ ≡ 148⋅148=21904 ≡ 268 mod 601

16: 519¹⁶=519⁸⁺⁸=519⁸⋅519⁸ ≡ 268⋅268=71824 ≡ 305 mod 601

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

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

254 = 128+64+32+16+8+4+2

572²⁵⁴

= 572^{128+64+32+16+8+4+2}

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

≡ 505 ⋅ 362 ⋅ 297 ⋅ 658 ⋅ 404 ⋅ 35 ⋅ 426 mod 821
≡ 182810 ⋅ 297 ⋅ 658 ⋅ 404 ⋅ 35 ⋅ 426 mod 821 ≡ 548 ⋅ 297 ⋅ 658 ⋅ 404 ⋅ 35 ⋅ 426 mod 821
≡ 162756 ⋅ 658 ⋅ 404 ⋅ 35 ⋅ 426 mod 821 ≡ 198 ⋅ 658 ⋅ 404 ⋅ 35 ⋅ 426 mod 821
≡ 130284 ⋅ 404 ⋅ 35 ⋅ 426 mod 821 ≡ 566 ⋅ 404 ⋅ 35 ⋅ 426 mod 821
≡ 228664 ⋅ 35 ⋅ 426 mod 821 ≡ 426 ⋅ 35 ⋅ 426 mod 821
≡ 14910 ⋅ 426 mod 821 ≡ 132 ⋅ 426 mod 821
≡ 56232 mod 821 ≡ 404 mod 821

Es gilt also: 572²⁵⁴ ≡ 404 mod 821

Berechnung des größten gemeinsamen Teilers von 59 und 22

=>59	= 2⋅22 + 15
=>22	= 1⋅15 + 7
=>15	= 2⋅7 + 1
=>7	= 7⋅1 + 0

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

Es gilt also: ggt(59,22)=1 = 3⋅59 -8⋅22

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

1 -3⋅59 = -8⋅22

-8⋅22 = -3⋅59 + 1 |+59⋅22

-8⋅22 + 59⋅22 = -3⋅59 + 59⋅22 + 1

(-8 + 59) ⋅ 22 = (-3 + 22) ⋅ 59 + 1

51⋅22 = 19⋅59 + 1

Es gilt also: 51⋅22 = 19⋅59 +1

Somit 51⋅22 = 1 mod 59

51 ist also das Inverse von 22 mod 59