Um längere Rechnungen zu vermeiden, rechnen wir:

(3503 - 7000) mod 7 ≡ (3503 mod 7 - 7000 mod 7) mod 7.

3503 mod 7 ≡ 3 mod 7 kann man relativ leicht bestimmen, weil ja 3503 = 3500+3 = 7 ⋅ 500 +3.

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

Somit gilt:

(3503 - 7000) mod 7 ≡ (3 - 0) mod 7 ≡ 3 mod 7.

Um längere Rechnungen zu vermeiden, rechnen wir:

(93 ⋅ 22) mod 9 ≡ (93 mod 9 ⋅ 22 mod 9) mod 9.

93 mod 9 ≡ 3 mod 9 kann man relativ leicht bestimmen, weil ja 93 = 90 + 3 = 10 ⋅ 9 + 3 ist.

22 mod 9 ≡ 4 mod 9 kann man relativ leicht bestimmen, weil ja 22 = 18 + 4 = 2 ⋅ 9 + 4 ist.

Somit gilt:

(93 ⋅ 22) mod 9 ≡ (3 ⋅ 4) mod 9 ≡ 12 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: 190¹=190

2: 190²=190¹⁺¹=190¹⋅190¹ ≡ 190⋅190=36100 ≡ 120 mod 257

4: 190⁴=190²⁺²=190²⋅190² ≡ 120⋅120=14400 ≡ 8 mod 257

8: 190⁸=190⁴⁺⁴=190⁴⋅190⁴ ≡ 8⋅8=64 ≡ 64 mod 257

16: 190¹⁶=190⁸⁺⁸=190⁸⋅190⁸ ≡ 64⋅64=4096 ≡ 241 mod 257

32: 190³²=190¹⁶⁺¹⁶=190¹⁶⋅190¹⁶ ≡ 241⋅241=58081 ≡ 256 mod 257

64: 190⁶⁴=190³²⁺³²=190³²⋅190³² ≡ 256⋅256=65536 ≡ 1 mod 257

128: 190¹²⁸=190⁶⁴⁺⁶⁴=190⁶⁴⋅190⁶⁴ ≡ 1⋅1=1 ≡ 1 mod 257

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

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

141 = 128+8+4+1

231¹⁴¹

= 231^128+8+4+1

= 231¹²⁸⋅231⁸⋅231⁴⋅231¹

≡ 401 ⋅ 48 ⋅ 116 ⋅ 231 mod 419
≡ 19248 ⋅ 116 ⋅ 231 mod 419 ≡ 393 ⋅ 116 ⋅ 231 mod 419
≡ 45588 ⋅ 231 mod 419 ≡ 336 ⋅ 231 mod 419
≡ 77616 mod 419 ≡ 101 mod 419

Es gilt also: 231¹⁴¹ ≡ 101 mod 419

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

=>53	= 1⋅35 + 18
=>35	= 1⋅18 + 17
=>18	= 1⋅17 + 1
=>17	= 17⋅1 + 0

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

Es gilt also: ggt(53,35)=1 = 2⋅53 -3⋅35

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

1 -2⋅53 = -3⋅35

-3⋅35 = -2⋅53 + 1 |+53⋅35

-3⋅35 + 53⋅35 = -2⋅53 + 53⋅35 + 1

(-3 + 53) ⋅ 35 = (-2 + 35) ⋅ 53 + 1

50⋅35 = 33⋅53 + 1

Es gilt also: 50⋅35 = 33⋅53 +1

Somit 50⋅35 = 1 mod 53

50 ist also das Inverse von 35 mod 53