Um längere Rechnungen zu vermeiden, rechnen wir:

(24004 - 407) mod 8 ≡ (24004 mod 8 - 407 mod 8) mod 8.

24004 mod 8 ≡ 4 mod 8 kann man relativ leicht bestimmen, weil ja 24004 = 24000+4 = 8 ⋅ 3000 +4.

407 mod 8 ≡ 7 mod 8 kann man relativ leicht bestimmen, weil ja 407 = 400+7 = 8 ⋅ 50 +7.

Somit gilt:

(24004 - 407) mod 8 ≡ (4 - 7) mod 8 ≡ -3 mod 8 ≡ 5 mod 8.

Um längere Rechnungen zu vermeiden, rechnen wir:

(27 ⋅ 75) mod 6 ≡ (27 mod 6 ⋅ 75 mod 6) mod 6.

27 mod 6 ≡ 3 mod 6 kann man relativ leicht bestimmen, weil ja 27 = 24 + 3 = 4 ⋅ 6 + 3 ist.

75 mod 6 ≡ 3 mod 6 kann man relativ leicht bestimmen, weil ja 75 = 72 + 3 = 12 ⋅ 6 + 3 ist.

Somit gilt:

(27 ⋅ 75) mod 6 ≡ (3 ⋅ 3) mod 6 ≡ 9 mod 6 ≡ 3 mod 6.

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

2: 250²=250¹⁺¹=250¹⋅250¹ ≡ 250⋅250=62500 ≡ 98 mod 761

4: 250⁴=250²⁺²=250²⋅250² ≡ 98⋅98=9604 ≡ 472 mod 761

8: 250⁸=250⁴⁺⁴=250⁴⋅250⁴ ≡ 472⋅472=222784 ≡ 572 mod 761

16: 250¹⁶=250⁸⁺⁸=250⁸⋅250⁸ ≡ 572⋅572=327184 ≡ 715 mod 761

32: 250³²=250¹⁶⁺¹⁶=250¹⁶⋅250¹⁶ ≡ 715⋅715=511225 ≡ 594 mod 761

64: 250⁶⁴=250³²⁺³²=250³²⋅250³² ≡ 594⋅594=352836 ≡ 493 mod 761

128: 250¹²⁸=250⁶⁴⁺⁶⁴=250⁶⁴⋅250⁶⁴ ≡ 493⋅493=243049 ≡ 290 mod 761

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

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

75 = 64+8+2+1

475⁷⁵

= 475^64+8+2+1

= 475⁶⁴⋅475⁸⋅475²⋅475¹

≡ 316 ⋅ 320 ⋅ 369 ⋅ 475 mod 761
≡ 101120 ⋅ 369 ⋅ 475 mod 761 ≡ 668 ⋅ 369 ⋅ 475 mod 761
≡ 246492 ⋅ 475 mod 761 ≡ 689 ⋅ 475 mod 761
≡ 327275 mod 761 ≡ 45 mod 761

Es gilt also: 475⁷⁵ ≡ 45 mod 761

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

=>97	= 1⋅52 + 45
=>52	= 1⋅45 + 7
=>45	= 6⋅7 + 3
=>7	= 2⋅3 + 1
=>3	= 3⋅1 + 0

also gilt: ggt(97,52)=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= 7-2⋅3
3= 45-6⋅7	eingesetzt in die Zeile drüber:	1	= 1⋅7 -2⋅(45 -6⋅ 7) = 1⋅7 -2⋅45 +12⋅ 7) = -2⋅45 +13⋅ 7 (=1)
7= 52-1⋅45	eingesetzt in die Zeile drüber:	1	= -2⋅45 +13⋅(52 -1⋅ 45) = -2⋅45 +13⋅52 -13⋅ 45) = 13⋅52 -15⋅ 45 (=1)
45= 97-1⋅52	eingesetzt in die Zeile drüber:	1	= 13⋅52 -15⋅(97 -1⋅ 52) = 13⋅52 -15⋅97 +15⋅ 52) = -15⋅97 +28⋅ 52 (=1)

Es gilt also: ggt(97,52)=1 = -15⋅97 +28⋅52

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

1 +15⋅97 = +28⋅52

Es gilt also: 28⋅52 = 15⋅97 +1

Somit 28⋅52 = 1 mod 97

28 ist also das Inverse von 52 mod 97