Um längere Rechnungen zu vermeiden, rechnen wir:

(98 + 25001) mod 5 ≡ (98 mod 5 + 25001 mod 5) mod 5.

98 mod 5 ≡ 3 mod 5 kann man relativ leicht bestimmen, weil ja 98 = 90+8 = 5 ⋅ 18 +8.

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

Somit gilt:

(98 + 25001) mod 5 ≡ (3 + 1) mod 5 ≡ 4 mod 5.

Um längere Rechnungen zu vermeiden, rechnen wir:

(22 ⋅ 39) mod 3 ≡ (22 mod 3 ⋅ 39 mod 3) mod 3.

22 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 22 = 21 + 1 = 7 ⋅ 3 + 1 ist.

39 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 39 = 39 + 0 = 13 ⋅ 3 + 0 ist.

Somit gilt:

(22 ⋅ 39) mod 3 ≡ (1 ⋅ 0) mod 3 ≡ 0 mod 3.

Die 64 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: 458¹=458

2: 458²=458¹⁺¹=458¹⋅458¹ ≡ 458⋅458=209764 ≡ 28 mod 971

4: 458⁴=458²⁺²=458²⋅458² ≡ 28⋅28=784 ≡ 784 mod 971

8: 458⁸=458⁴⁺⁴=458⁴⋅458⁴ ≡ 784⋅784=614656 ≡ 13 mod 971

16: 458¹⁶=458⁸⁺⁸=458⁸⋅458⁸ ≡ 13⋅13=169 ≡ 169 mod 971

32: 458³²=458¹⁶⁺¹⁶=458¹⁶⋅458¹⁶ ≡ 169⋅169=28561 ≡ 402 mod 971

64: 458⁶⁴=458³²⁺³²=458³²⋅458³² ≡ 402⋅402=161604 ≡ 418 mod 971

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

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

254 = 128+64+32+16+8+4+2

318²⁵⁴

= 318^{128+64+32+16+8+4+2}

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

≡ 329 ⋅ 160 ⋅ 636 ⋅ 479 ⋅ 116 ⋅ 234 ⋅ 40 mod 683
≡ 52640 ⋅ 636 ⋅ 479 ⋅ 116 ⋅ 234 ⋅ 40 mod 683 ≡ 49 ⋅ 636 ⋅ 479 ⋅ 116 ⋅ 234 ⋅ 40 mod 683
≡ 31164 ⋅ 479 ⋅ 116 ⋅ 234 ⋅ 40 mod 683 ≡ 429 ⋅ 479 ⋅ 116 ⋅ 234 ⋅ 40 mod 683
≡ 205491 ⋅ 116 ⋅ 234 ⋅ 40 mod 683 ≡ 591 ⋅ 116 ⋅ 234 ⋅ 40 mod 683
≡ 68556 ⋅ 234 ⋅ 40 mod 683 ≡ 256 ⋅ 234 ⋅ 40 mod 683
≡ 59904 ⋅ 40 mod 683 ≡ 483 ⋅ 40 mod 683
≡ 19320 mod 683 ≡ 196 mod 683

Es gilt also: 318²⁵⁴ ≡ 196 mod 683

Berechnung des größten gemeinsamen Teilers von 61 und 24

=>61	= 2⋅24 + 13
=>24	= 1⋅13 + 11
=>13	= 1⋅11 + 2
=>11	= 5⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(61,24)=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= 11-5⋅2
2= 13-1⋅11	eingesetzt in die Zeile drüber:	1	= 1⋅11 -5⋅(13 -1⋅ 11) = 1⋅11 -5⋅13 +5⋅ 11) = -5⋅13 +6⋅ 11 (=1)
11= 24-1⋅13	eingesetzt in die Zeile drüber:	1	= -5⋅13 +6⋅(24 -1⋅ 13) = -5⋅13 +6⋅24 -6⋅ 13) = 6⋅24 -11⋅ 13 (=1)
13= 61-2⋅24	eingesetzt in die Zeile drüber:	1	= 6⋅24 -11⋅(61 -2⋅ 24) = 6⋅24 -11⋅61 +22⋅ 24) = -11⋅61 +28⋅ 24 (=1)

Es gilt also: ggt(61,24)=1 = -11⋅61 +28⋅24

oder wenn man -11⋅61 auf die linke Seite bringt:

1 +11⋅61 = +28⋅24

Es gilt also: 28⋅24 = 11⋅61 +1

Somit 28⋅24 = 1 mod 61

28 ist also das Inverse von 24 mod 61