Um längere Rechnungen zu vermeiden, rechnen wir:

(84 - 1601) mod 4 ≡ (84 mod 4 - 1601 mod 4) mod 4.

84 mod 4 ≡ 0 mod 4 kann man relativ leicht bestimmen, weil ja 84 = 80+4 = 4 ⋅ 20 +4.

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

Somit gilt:

(84 - 1601) mod 4 ≡ (0 - 1) mod 4 ≡ -1 mod 4 ≡ 3 mod 4.

Um längere Rechnungen zu vermeiden, rechnen wir:

(47 ⋅ 23) mod 7 ≡ (47 mod 7 ⋅ 23 mod 7) mod 7.

47 mod 7 ≡ 5 mod 7 kann man relativ leicht bestimmen, weil ja 47 = 42 + 5 = 6 ⋅ 7 + 5 ist.

23 mod 7 ≡ 2 mod 7 kann man relativ leicht bestimmen, weil ja 23 = 21 + 2 = 3 ⋅ 7 + 2 ist.

Somit gilt:

(47 ⋅ 23) mod 7 ≡ (5 ⋅ 2) mod 7 ≡ 10 mod 7 ≡ 3 mod 7.

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

2: 639²=639¹⁺¹=639¹⋅639¹ ≡ 639⋅639=408321 ≡ 912 mod 977

4: 639⁴=639²⁺²=639²⋅639² ≡ 912⋅912=831744 ≡ 317 mod 977

8: 639⁸=639⁴⁺⁴=639⁴⋅639⁴ ≡ 317⋅317=100489 ≡ 835 mod 977

16: 639¹⁶=639⁸⁺⁸=639⁸⋅639⁸ ≡ 835⋅835=697225 ≡ 624 mod 977

32: 639³²=639¹⁶⁺¹⁶=639¹⁶⋅639¹⁶ ≡ 624⋅624=389376 ≡ 530 mod 977

64: 639⁶⁴=639³²⁺³²=639³²⋅639³² ≡ 530⋅530=280900 ≡ 501 mod 977

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

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

227 = 128+64+32+2+1

619²²⁷

= 619^{128+64+32+2+1}

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

≡ 191 ⋅ 807 ⋅ 115 ⋅ 864 ⋅ 619 mod 887
≡ 154137 ⋅ 115 ⋅ 864 ⋅ 619 mod 887 ≡ 686 ⋅ 115 ⋅ 864 ⋅ 619 mod 887
≡ 78890 ⋅ 864 ⋅ 619 mod 887 ≡ 834 ⋅ 864 ⋅ 619 mod 887
≡ 720576 ⋅ 619 mod 887 ≡ 332 ⋅ 619 mod 887
≡ 205508 mod 887 ≡ 611 mod 887

Es gilt also: 619²²⁷ ≡ 611 mod 887

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

=>53	= 1⋅28 + 25
=>28	= 1⋅25 + 3
=>25	= 8⋅3 + 1
=>3	= 3⋅1 + 0

also gilt: ggt(53,28)=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= 25-8⋅3
3= 28-1⋅25	eingesetzt in die Zeile drüber:	1	= 1⋅25 -8⋅(28 -1⋅ 25) = 1⋅25 -8⋅28 +8⋅ 25) = -8⋅28 +9⋅ 25 (=1)
25= 53-1⋅28	eingesetzt in die Zeile drüber:	1	= -8⋅28 +9⋅(53 -1⋅ 28) = -8⋅28 +9⋅53 -9⋅ 28) = 9⋅53 -17⋅ 28 (=1)

Es gilt also: ggt(53,28)=1 = 9⋅53 -17⋅28

oder wenn man 9⋅53 auf die linke Seite bringt:

1 -9⋅53 = -17⋅28

-17⋅28 = -9⋅53 + 1 |+53⋅28

-17⋅28 + 53⋅28 = -9⋅53 + 53⋅28 + 1

(-17 + 53) ⋅ 28 = (-9 + 28) ⋅ 53 + 1

36⋅28 = 19⋅53 + 1

Es gilt also: 36⋅28 = 19⋅53 +1

Somit 36⋅28 = 1 mod 53

36 ist also das Inverse von 28 mod 53