Um längere Rechnungen zu vermeiden, rechnen wir:

(200 - 19996) mod 4 ≡ (200 mod 4 - 19996 mod 4) mod 4.

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

19996 mod 4 ≡ 0 mod 4 kann man relativ leicht bestimmen, weil ja 19996 = 19000+996 = 4 ⋅ 4750 +996.

Somit gilt:

(200 - 19996) mod 4 ≡ (0 - 0) mod 4 ≡ 0 mod 4.

Um längere Rechnungen zu vermeiden, rechnen wir:

(25 ⋅ 63) mod 10 ≡ (25 mod 10 ⋅ 63 mod 10) mod 10.

25 mod 10 ≡ 5 mod 10 kann man relativ leicht bestimmen, weil ja 25 = 20 + 5 = 2 ⋅ 10 + 5 ist.

63 mod 10 ≡ 3 mod 10 kann man relativ leicht bestimmen, weil ja 63 = 60 + 3 = 6 ⋅ 10 + 3 ist.

Somit gilt:

(25 ⋅ 63) mod 10 ≡ (5 ⋅ 3) mod 10 ≡ 15 mod 10 ≡ 5 mod 10.

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

2: 149²=149¹⁺¹=149¹⋅149¹ ≡ 149⋅149=22201 ≡ 291 mod 313

4: 149⁴=149²⁺²=149²⋅149² ≡ 291⋅291=84681 ≡ 171 mod 313

8: 149⁸=149⁴⁺⁴=149⁴⋅149⁴ ≡ 171⋅171=29241 ≡ 132 mod 313

16: 149¹⁶=149⁸⁺⁸=149⁸⋅149⁸ ≡ 132⋅132=17424 ≡ 209 mod 313

32: 149³²=149¹⁶⁺¹⁶=149¹⁶⋅149¹⁶ ≡ 209⋅209=43681 ≡ 174 mod 313

64: 149⁶⁴=149³²⁺³²=149³²⋅149³² ≡ 174⋅174=30276 ≡ 228 mod 313

128: 149¹²⁸=149⁶⁴⁺⁶⁴=149⁶⁴⋅149⁶⁴ ≡ 228⋅228=51984 ≡ 26 mod 313

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

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

112 = 64+32+16

330¹¹²

= 330^64+32+16

= 330⁶⁴⋅330³²⋅330¹⁶

≡ 127 ⋅ 109 ⋅ 343 mod 653
≡ 13843 ⋅ 343 mod 653 ≡ 130 ⋅ 343 mod 653
≡ 44590 mod 653 ≡ 186 mod 653

Es gilt also: 330¹¹² ≡ 186 mod 653

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

=>101	= 1⋅59 + 42
=>59	= 1⋅42 + 17
=>42	= 2⋅17 + 8
=>17	= 2⋅8 + 1
=>8	= 8⋅1 + 0

also gilt: ggt(101,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= 17-2⋅8
8= 42-2⋅17	eingesetzt in die Zeile drüber:	1	= 1⋅17 -2⋅(42 -2⋅ 17) = 1⋅17 -2⋅42 +4⋅ 17) = -2⋅42 +5⋅ 17 (=1)
17= 59-1⋅42	eingesetzt in die Zeile drüber:	1	= -2⋅42 +5⋅(59 -1⋅ 42) = -2⋅42 +5⋅59 -5⋅ 42) = 5⋅59 -7⋅ 42 (=1)
42= 101-1⋅59	eingesetzt in die Zeile drüber:	1	= 5⋅59 -7⋅(101 -1⋅ 59) = 5⋅59 -7⋅101 +7⋅ 59) = -7⋅101 +12⋅ 59 (=1)

Es gilt also: ggt(101,59)=1 = -7⋅101 +12⋅59

oder wenn man -7⋅101 auf die linke Seite bringt:

1 +7⋅101 = +12⋅59

Es gilt also: 12⋅59 = 7⋅101 +1

Somit 12⋅59 = 1 mod 101

12 ist also das Inverse von 59 mod 101