Um längere Rechnungen zu vermeiden, rechnen wir:

(401 - 1204) mod 4 ≡ (401 mod 4 - 1204 mod 4) mod 4.

401 mod 4 ≡ 1 mod 4 kann man relativ leicht bestimmen, weil ja 401 = 400+1 = 4 ⋅ 100 +1.

1204 mod 4 ≡ 0 mod 4 kann man relativ leicht bestimmen, weil ja 1204 = 1200+4 = 4 ⋅ 300 +4.

Somit gilt:

(401 - 1204) mod 4 ≡ (1 - 0) mod 4 ≡ 1 mod 4.

Um längere Rechnungen zu vermeiden, rechnen wir:

(47 ⋅ 44) mod 11 ≡ (47 mod 11 ⋅ 44 mod 11) mod 11.

47 mod 11 ≡ 3 mod 11 kann man relativ leicht bestimmen, weil ja 47 = 44 + 3 = 4 ⋅ 11 + 3 ist.

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

Somit gilt:

(47 ⋅ 44) mod 11 ≡ (3 ⋅ 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: 562¹=562

2: 562²=562¹⁺¹=562¹⋅562¹ ≡ 562⋅562=315844 ≡ 613 mod 883

4: 562⁴=562²⁺²=562²⋅562² ≡ 613⋅613=375769 ≡ 494 mod 883

8: 562⁸=562⁴⁺⁴=562⁴⋅562⁴ ≡ 494⋅494=244036 ≡ 328 mod 883

16: 562¹⁶=562⁸⁺⁸=562⁸⋅562⁸ ≡ 328⋅328=107584 ≡ 741 mod 883

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

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

220 = 128+64+16+8+4

566²²⁰

= 566^{128+64+16+8+4}

= 566¹²⁸⋅566⁶⁴⋅566¹⁶⋅566⁸⋅566⁴

≡ 812 ⋅ 277 ⋅ 303 ⋅ 819 ⋅ 198 mod 853
≡ 224924 ⋅ 303 ⋅ 819 ⋅ 198 mod 853 ≡ 585 ⋅ 303 ⋅ 819 ⋅ 198 mod 853
≡ 177255 ⋅ 819 ⋅ 198 mod 853 ≡ 684 ⋅ 819 ⋅ 198 mod 853
≡ 560196 ⋅ 198 mod 853 ≡ 628 ⋅ 198 mod 853
≡ 124344 mod 853 ≡ 659 mod 853

Es gilt also: 566²²⁰ ≡ 659 mod 853

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

=>73	= 1⋅59 + 14
=>59	= 4⋅14 + 3
=>14	= 4⋅3 + 2
=>3	= 1⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(73,59)=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= 3-1⋅2
2= 14-4⋅3	eingesetzt in die Zeile drüber:	1	= 1⋅3 -1⋅(14 -4⋅ 3) = 1⋅3 -1⋅14 +4⋅ 3) = -1⋅14 +5⋅ 3 (=1)
3= 59-4⋅14	eingesetzt in die Zeile drüber:	1	= -1⋅14 +5⋅(59 -4⋅ 14) = -1⋅14 +5⋅59 -20⋅ 14) = 5⋅59 -21⋅ 14 (=1)
14= 73-1⋅59	eingesetzt in die Zeile drüber:	1	= 5⋅59 -21⋅(73 -1⋅ 59) = 5⋅59 -21⋅73 +21⋅ 59) = -21⋅73 +26⋅ 59 (=1)

Es gilt also: ggt(73,59)=1 = -21⋅73 +26⋅59

oder wenn man -21⋅73 auf die linke Seite bringt:

1 +21⋅73 = +26⋅59

Es gilt also: 26⋅59 = 21⋅73 +1

Somit 26⋅59 = 1 mod 73

26 ist also das Inverse von 59 mod 73