Um längere Rechnungen zu vermeiden, rechnen wir:

(2503 - 2001) mod 5 ≡ (2503 mod 5 - 2001 mod 5) mod 5.

2503 mod 5 ≡ 3 mod 5 kann man relativ leicht bestimmen, weil ja 2503 = 2500+3 = 5 ⋅ 500 +3.

2001 mod 5 ≡ 1 mod 5 kann man relativ leicht bestimmen, weil ja 2001 = 2000+1 = 5 ⋅ 400 +1.

Somit gilt:

(2503 - 2001) mod 5 ≡ (3 - 1) mod 5 ≡ 2 mod 5.

Um längere Rechnungen zu vermeiden, rechnen wir:

(71 ⋅ 42) mod 9 ≡ (71 mod 9 ⋅ 42 mod 9) mod 9.

71 mod 9 ≡ 8 mod 9 kann man relativ leicht bestimmen, weil ja 71 = 63 + 8 = 7 ⋅ 9 + 8 ist.

42 mod 9 ≡ 6 mod 9 kann man relativ leicht bestimmen, weil ja 42 = 36 + 6 = 4 ⋅ 9 + 6 ist.

Somit gilt:

(71 ⋅ 42) mod 9 ≡ (8 ⋅ 6) mod 9 ≡ 48 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: 471¹=471

2: 471²=471¹⁺¹=471¹⋅471¹ ≡ 471⋅471=221841 ≡ 542 mod 587

4: 471⁴=471²⁺²=471²⋅471² ≡ 542⋅542=293764 ≡ 264 mod 587

8: 471⁸=471⁴⁺⁴=471⁴⋅471⁴ ≡ 264⋅264=69696 ≡ 430 mod 587

16: 471¹⁶=471⁸⁺⁸=471⁸⋅471⁸ ≡ 430⋅430=184900 ≡ 582 mod 587

32: 471³²=471¹⁶⁺¹⁶=471¹⁶⋅471¹⁶ ≡ 582⋅582=338724 ≡ 25 mod 587

64: 471⁶⁴=471³²⁺³²=471³²⋅471³² ≡ 25⋅25=625 ≡ 38 mod 587

128: 471¹²⁸=471⁶⁴⁺⁶⁴=471⁶⁴⋅471⁶⁴ ≡ 38⋅38=1444 ≡ 270 mod 587

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

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

201 = 128+64+8+1

175²⁰¹

= 175^128+64+8+1

= 175¹²⁸⋅175⁶⁴⋅175⁸⋅175¹

≡ 381 ⋅ 101 ⋅ 381 ⋅ 175 mod 491
≡ 38481 ⋅ 381 ⋅ 175 mod 491 ≡ 183 ⋅ 381 ⋅ 175 mod 491
≡ 69723 ⋅ 175 mod 491 ≡ 1 ⋅ 175 mod 491
≡ 175 mod 491

Es gilt also: 175²⁰¹ ≡ 175 mod 491

Berechnung des größten gemeinsamen Teilers von 97 und 75

=>97	= 1⋅75 + 22
=>75	= 3⋅22 + 9
=>22	= 2⋅9 + 4
=>9	= 2⋅4 + 1
=>4	= 4⋅1 + 0

also gilt: ggt(97,75)=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= 9-2⋅4
4= 22-2⋅9	eingesetzt in die Zeile drüber:	1	= 1⋅9 -2⋅(22 -2⋅ 9) = 1⋅9 -2⋅22 +4⋅ 9) = -2⋅22 +5⋅ 9 (=1)
9= 75-3⋅22	eingesetzt in die Zeile drüber:	1	= -2⋅22 +5⋅(75 -3⋅ 22) = -2⋅22 +5⋅75 -15⋅ 22) = 5⋅75 -17⋅ 22 (=1)
22= 97-1⋅75	eingesetzt in die Zeile drüber:	1	= 5⋅75 -17⋅(97 -1⋅ 75) = 5⋅75 -17⋅97 +17⋅ 75) = -17⋅97 +22⋅ 75 (=1)

Es gilt also: ggt(97,75)=1 = -17⋅97 +22⋅75

oder wenn man -17⋅97 auf die linke Seite bringt:

1 +17⋅97 = +22⋅75

Es gilt also: 22⋅75 = 17⋅97 +1

Somit 22⋅75 = 1 mod 97

22 ist also das Inverse von 75 mod 97