Um längere Rechnungen zu vermeiden, rechnen wir:

(24996 + 195) mod 5 ≡ (24996 mod 5 + 195 mod 5) mod 5.

24996 mod 5 ≡ 1 mod 5 kann man relativ leicht bestimmen, weil ja 24996 = 24000+996 = 5 ⋅ 4800 +996.

195 mod 5 ≡ 0 mod 5 kann man relativ leicht bestimmen, weil ja 195 = 190+5 = 5 ⋅ 38 +5.

Somit gilt:

(24996 + 195) mod 5 ≡ (1 + 0) mod 5 ≡ 1 mod 5.

Um längere Rechnungen zu vermeiden, rechnen wir:

(55 ⋅ 20) mod 3 ≡ (55 mod 3 ⋅ 20 mod 3) mod 3.

55 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 55 = 54 + 1 = 18 ⋅ 3 + 1 ist.

20 mod 3 ≡ 2 mod 3 kann man relativ leicht bestimmen, weil ja 20 = 18 + 2 = 6 ⋅ 3 + 2 ist.

Somit gilt:

(55 ⋅ 20) mod 3 ≡ (1 ⋅ 2) mod 3 ≡ 2 mod 3.

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

2: 501²=501¹⁺¹=501¹⋅501¹ ≡ 501⋅501=251001 ≡ 822 mod 937

4: 501⁴=501²⁺²=501²⋅501² ≡ 822⋅822=675684 ≡ 107 mod 937

8: 501⁸=501⁴⁺⁴=501⁴⋅501⁴ ≡ 107⋅107=11449 ≡ 205 mod 937

16: 501¹⁶=501⁸⁺⁸=501⁸⋅501⁸ ≡ 205⋅205=42025 ≡ 797 mod 937

32: 501³²=501¹⁶⁺¹⁶=501¹⁶⋅501¹⁶ ≡ 797⋅797=635209 ≡ 860 mod 937

64: 501⁶⁴=501³²⁺³²=501³²⋅501³² ≡ 860⋅860=739600 ≡ 307 mod 937

128: 501¹²⁸=501⁶⁴⁺⁶⁴=501⁶⁴⋅501⁶⁴ ≡ 307⋅307=94249 ≡ 549 mod 937

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

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

208 = 128+64+16

231²⁰⁸

= 231^128+64+16

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

≡ 24 ⋅ 39 ⋅ 391 mod 499
≡ 936 ⋅ 391 mod 499 ≡ 437 ⋅ 391 mod 499
≡ 170867 mod 499 ≡ 209 mod 499

Es gilt also: 231²⁰⁸ ≡ 209 mod 499

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

=>97	= 2⋅42 + 13
=>42	= 3⋅13 + 3
=>13	= 4⋅3 + 1
=>3	= 3⋅1 + 0

also gilt: ggt(97,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= 42-3⋅13	eingesetzt in die Zeile drüber:	1	= 1⋅13 -4⋅(42 -3⋅ 13) = 1⋅13 -4⋅42 +12⋅ 13) = -4⋅42 +13⋅ 13 (=1)
13= 97-2⋅42	eingesetzt in die Zeile drüber:	1	= -4⋅42 +13⋅(97 -2⋅ 42) = -4⋅42 +13⋅97 -26⋅ 42) = 13⋅97 -30⋅ 42 (=1)

Es gilt also: ggt(97,42)=1 = 13⋅97 -30⋅42

oder wenn man 13⋅97 auf die linke Seite bringt:

1 -13⋅97 = -30⋅42

-30⋅42 = -13⋅97 + 1 |+97⋅42

-30⋅42 + 97⋅42 = -13⋅97 + 97⋅42 + 1

(-30 + 97) ⋅ 42 = (-13 + 42) ⋅ 97 + 1

67⋅42 = 29⋅97 + 1

Es gilt also: 67⋅42 = 29⋅97 +1

Somit 67⋅42 = 1 mod 97

67 ist also das Inverse von 42 mod 97