Um längere Rechnungen zu vermeiden, rechnen wir:

(25004 + 10001) mod 5 ≡ (25004 mod 5 + 10001 mod 5) mod 5.

25004 mod 5 ≡ 4 mod 5 kann man relativ leicht bestimmen, weil ja 25004 = 25000+4 = 5 ⋅ 5000 +4.

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

Somit gilt:

(25004 + 10001) mod 5 ≡ (4 + 1) mod 5 ≡ 5 mod 5 ≡ 0 mod 5.

Um längere Rechnungen zu vermeiden, rechnen wir:

(67 ⋅ 53) mod 5 ≡ (67 mod 5 ⋅ 53 mod 5) mod 5.

67 mod 5 ≡ 2 mod 5 kann man relativ leicht bestimmen, weil ja 67 = 65 + 2 = 13 ⋅ 5 + 2 ist.

53 mod 5 ≡ 3 mod 5 kann man relativ leicht bestimmen, weil ja 53 = 50 + 3 = 10 ⋅ 5 + 3 ist.

Somit gilt:

(67 ⋅ 53) mod 5 ≡ (2 ⋅ 3) mod 5 ≡ 6 mod 5 ≡ 1 mod 5.

Die 32 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: 939¹=939

2: 939²=939¹⁺¹=939¹⋅939¹ ≡ 939⋅939=881721 ≡ 4 mod 941

4: 939⁴=939²⁺²=939²⋅939² ≡ 4⋅4=16 ≡ 16 mod 941

8: 939⁸=939⁴⁺⁴=939⁴⋅939⁴ ≡ 16⋅16=256 ≡ 256 mod 941

16: 939¹⁶=939⁸⁺⁸=939⁸⋅939⁸ ≡ 256⋅256=65536 ≡ 607 mod 941

32: 939³²=939¹⁶⁺¹⁶=939¹⁶⋅939¹⁶ ≡ 607⋅607=368449 ≡ 518 mod 941

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

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

238 = 128+64+32+8+4+2

513²³⁸

= 513^{128+64+32+8+4+2}

= 513¹²⁸⋅513⁶⁴⋅513³²⋅513⁸⋅513⁴⋅513²

≡ 285 ⋅ 204 ⋅ 250 ⋅ 526 ⋅ 136 ⋅ 208 mod 599
≡ 58140 ⋅ 250 ⋅ 526 ⋅ 136 ⋅ 208 mod 599 ≡ 37 ⋅ 250 ⋅ 526 ⋅ 136 ⋅ 208 mod 599
≡ 9250 ⋅ 526 ⋅ 136 ⋅ 208 mod 599 ≡ 265 ⋅ 526 ⋅ 136 ⋅ 208 mod 599
≡ 139390 ⋅ 136 ⋅ 208 mod 599 ≡ 422 ⋅ 136 ⋅ 208 mod 599
≡ 57392 ⋅ 208 mod 599 ≡ 487 ⋅ 208 mod 599
≡ 101296 mod 599 ≡ 65 mod 599

Es gilt also: 513²³⁸ ≡ 65 mod 599

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

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

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

Es gilt also: ggt(101,42)=1 = 5⋅101 -12⋅42

oder wenn man 5⋅101 auf die linke Seite bringt:

1 -5⋅101 = -12⋅42

-12⋅42 = -5⋅101 + 1 |+101⋅42

-12⋅42 + 101⋅42 = -5⋅101 + 101⋅42 + 1

(-12 + 101) ⋅ 42 = (-5 + 42) ⋅ 101 + 1

89⋅42 = 37⋅101 + 1

Es gilt also: 89⋅42 = 37⋅101 +1

Somit 89⋅42 = 1 mod 101

89 ist also das Inverse von 42 mod 101