Um längere Rechnungen zu vermeiden, rechnen wir:

(202 - 16004) mod 4 ≡ (202 mod 4 - 16004 mod 4) mod 4.

202 mod 4 ≡ 2 mod 4 kann man relativ leicht bestimmen, weil ja 202 = 200+2 = 4 ⋅ 50 +2.

16004 mod 4 ≡ 0 mod 4 kann man relativ leicht bestimmen, weil ja 16004 = 16000+4 = 4 ⋅ 4000 +4.

Somit gilt:

(202 - 16004) mod 4 ≡ (2 - 0) mod 4 ≡ 2 mod 4.

Um längere Rechnungen zu vermeiden, rechnen wir:

(61 ⋅ 30) mod 9 ≡ (61 mod 9 ⋅ 30 mod 9) mod 9.

61 mod 9 ≡ 7 mod 9 kann man relativ leicht bestimmen, weil ja 61 = 54 + 7 = 6 ⋅ 9 + 7 ist.

30 mod 9 ≡ 3 mod 9 kann man relativ leicht bestimmen, weil ja 30 = 27 + 3 = 3 ⋅ 9 + 3 ist.

Somit gilt:

(61 ⋅ 30) mod 9 ≡ (7 ⋅ 3) mod 9 ≡ 21 mod 9 ≡ 3 mod 9.

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

2: 446²=446¹⁺¹=446¹⋅446¹ ≡ 446⋅446=198916 ≡ 176 mod 523

4: 446⁴=446²⁺²=446²⋅446² ≡ 176⋅176=30976 ≡ 119 mod 523

8: 446⁸=446⁴⁺⁴=446⁴⋅446⁴ ≡ 119⋅119=14161 ≡ 40 mod 523

16: 446¹⁶=446⁸⁺⁸=446⁸⋅446⁸ ≡ 40⋅40=1600 ≡ 31 mod 523

32: 446³²=446¹⁶⁺¹⁶=446¹⁶⋅446¹⁶ ≡ 31⋅31=961 ≡ 438 mod 523

64: 446⁶⁴=446³²⁺³²=446³²⋅446³² ≡ 438⋅438=191844 ≡ 426 mod 523

128: 446¹²⁸=446⁶⁴⁺⁶⁴=446⁶⁴⋅446⁶⁴ ≡ 426⋅426=181476 ≡ 518 mod 523

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

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

219 = 128+64+16+8+2+1

783²¹⁹

= 783^{128+64+16+8+2+1}

= 783¹²⁸⋅783⁶⁴⋅783¹⁶⋅783⁸⋅783²⋅783¹

≡ 295 ⋅ 817 ⋅ 884 ⋅ 718 ⋅ 116 ⋅ 783 mod 919
≡ 241015 ⋅ 884 ⋅ 718 ⋅ 116 ⋅ 783 mod 919 ≡ 237 ⋅ 884 ⋅ 718 ⋅ 116 ⋅ 783 mod 919
≡ 209508 ⋅ 718 ⋅ 116 ⋅ 783 mod 919 ≡ 895 ⋅ 718 ⋅ 116 ⋅ 783 mod 919
≡ 642610 ⋅ 116 ⋅ 783 mod 919 ≡ 229 ⋅ 116 ⋅ 783 mod 919
≡ 26564 ⋅ 783 mod 919 ≡ 832 ⋅ 783 mod 919
≡ 651456 mod 919 ≡ 804 mod 919

Es gilt also: 783²¹⁹ ≡ 804 mod 919

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

=>71	= 1⋅42 + 29
=>42	= 1⋅29 + 13
=>29	= 2⋅13 + 3
=>13	= 4⋅3 + 1
=>3	= 3⋅1 + 0

also gilt: ggt(71,42)=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= 13-4⋅3
3= 29-2⋅13	eingesetzt in die Zeile drüber:	1	= 1⋅13 -4⋅(29 -2⋅ 13) = 1⋅13 -4⋅29 +8⋅ 13) = -4⋅29 +9⋅ 13 (=1)
13= 42-1⋅29	eingesetzt in die Zeile drüber:	1	= -4⋅29 +9⋅(42 -1⋅ 29) = -4⋅29 +9⋅42 -9⋅ 29) = 9⋅42 -13⋅ 29 (=1)
29= 71-1⋅42	eingesetzt in die Zeile drüber:	1	= 9⋅42 -13⋅(71 -1⋅ 42) = 9⋅42 -13⋅71 +13⋅ 42) = -13⋅71 +22⋅ 42 (=1)

Es gilt also: ggt(71,42)=1 = -13⋅71 +22⋅42

oder wenn man -13⋅71 auf die linke Seite bringt:

1 +13⋅71 = +22⋅42

Es gilt also: 22⋅42 = 13⋅71 +1

Somit 22⋅42 = 1 mod 71

22 ist also das Inverse von 42 mod 71