Um längere Rechnungen zu vermeiden, rechnen wir:

(23994 - 24001) mod 6 ≡ (23994 mod 6 - 24001 mod 6) mod 6.

23994 mod 6 ≡ 0 mod 6 kann man relativ leicht bestimmen, weil ja 23994 = 24000-6 = 6 ⋅ 4000 -6 = 6 ⋅ 4000 - 6 + 0.

24001 mod 6 ≡ 1 mod 6 kann man relativ leicht bestimmen, weil ja 24001 = 24000+1 = 6 ⋅ 4000 +1.

Somit gilt:

(23994 - 24001) mod 6 ≡ (0 - 1) mod 6 ≡ -1 mod 6 ≡ 5 mod 6.

Um längere Rechnungen zu vermeiden, rechnen wir:

(77 ⋅ 96) mod 7 ≡ (77 mod 7 ⋅ 96 mod 7) mod 7.

77 mod 7 ≡ 0 mod 7 kann man relativ leicht bestimmen, weil ja 77 = 77 + 0 = 11 ⋅ 7 + 0 ist.

96 mod 7 ≡ 5 mod 7 kann man relativ leicht bestimmen, weil ja 96 = 91 + 5 = 13 ⋅ 7 + 5 ist.

Somit gilt:

(77 ⋅ 96) mod 7 ≡ (0 ⋅ 5) mod 7 ≡ 0 mod 7.

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

2: 435²=435¹⁺¹=435¹⋅435¹ ≡ 435⋅435=189225 ≡ 20 mod 479

4: 435⁴=435²⁺²=435²⋅435² ≡ 20⋅20=400 ≡ 400 mod 479

8: 435⁸=435⁴⁺⁴=435⁴⋅435⁴ ≡ 400⋅400=160000 ≡ 14 mod 479

16: 435¹⁶=435⁸⁺⁸=435⁸⋅435⁸ ≡ 14⋅14=196 ≡ 196 mod 479

32: 435³²=435¹⁶⁺¹⁶=435¹⁶⋅435¹⁶ ≡ 196⋅196=38416 ≡ 96 mod 479

64: 435⁶⁴=435³²⁺³²=435³²⋅435³² ≡ 96⋅96=9216 ≡ 115 mod 479

128: 435¹²⁸=435⁶⁴⁺⁶⁴=435⁶⁴⋅435⁶⁴ ≡ 115⋅115=13225 ≡ 292 mod 479

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

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

167 = 128+32+4+2+1

183¹⁶⁷

= 183^128+32+4+2+1

= 183¹²⁸⋅183³²⋅183⁴⋅183²⋅183¹

≡ 1 ⋅ 1 ⋅ 254 ⋅ 148 ⋅ 183 mod 433
≡ 1 ⋅ 254 ⋅ 148 ⋅ 183 mod 433
≡ 254 ⋅ 148 ⋅ 183 mod 433
≡ 37592 ⋅ 183 mod 433 ≡ 354 ⋅ 183 mod 433
≡ 64782 mod 433 ≡ 265 mod 433

Es gilt also: 183¹⁶⁷ ≡ 265 mod 433

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

=>97	= 1⋅50 + 47
=>50	= 1⋅47 + 3
=>47	= 15⋅3 + 2
=>3	= 1⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(97,50)=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= 3-1⋅2
2= 47-15⋅3	eingesetzt in die Zeile drüber:	1	= 1⋅3 -1⋅(47 -15⋅ 3) = 1⋅3 -1⋅47 +15⋅ 3) = -1⋅47 +16⋅ 3 (=1)
3= 50-1⋅47	eingesetzt in die Zeile drüber:	1	= -1⋅47 +16⋅(50 -1⋅ 47) = -1⋅47 +16⋅50 -16⋅ 47) = 16⋅50 -17⋅ 47 (=1)
47= 97-1⋅50	eingesetzt in die Zeile drüber:	1	= 16⋅50 -17⋅(97 -1⋅ 50) = 16⋅50 -17⋅97 +17⋅ 50) = -17⋅97 +33⋅ 50 (=1)

Es gilt also: ggt(97,50)=1 = -17⋅97 +33⋅50

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

1 +17⋅97 = +33⋅50

Es gilt also: 33⋅50 = 17⋅97 +1

Somit 33⋅50 = 1 mod 97

33 ist also das Inverse von 50 mod 97