Um längere Rechnungen zu vermeiden, rechnen wir:

(23996 + 2399) mod 6 ≡ (23996 mod 6 + 2399 mod 6) mod 6.

23996 mod 6 ≡ 2 mod 6 kann man relativ leicht bestimmen, weil ja 23996 = 24000-4 = 6 ⋅ 4000 -4 = 6 ⋅ 4000 - 6 + 2.

2399 mod 6 ≡ 5 mod 6 kann man relativ leicht bestimmen, weil ja 2399 = 2400-1 = 6 ⋅ 400 -1 = 6 ⋅ 400 - 6 + 5.

Somit gilt:

(23996 + 2399) mod 6 ≡ (2 + 5) mod 6 ≡ 7 mod 6 ≡ 1 mod 6.

Um längere Rechnungen zu vermeiden, rechnen wir:

(32 ⋅ 67) mod 11 ≡ (32 mod 11 ⋅ 67 mod 11) mod 11.

32 mod 11 ≡ 10 mod 11 kann man relativ leicht bestimmen, weil ja 32 = 22 + 10 = 2 ⋅ 11 + 10 ist.

67 mod 11 ≡ 1 mod 11 kann man relativ leicht bestimmen, weil ja 67 = 66 + 1 = 6 ⋅ 11 + 1 ist.

Somit gilt:

(32 ⋅ 67) mod 11 ≡ (10 ⋅ 1) mod 11 ≡ 10 mod 11.

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

2: 515²=515¹⁺¹=515¹⋅515¹ ≡ 515⋅515=265225 ≡ 93 mod 557

4: 515⁴=515²⁺²=515²⋅515² ≡ 93⋅93=8649 ≡ 294 mod 557

8: 515⁸=515⁴⁺⁴=515⁴⋅515⁴ ≡ 294⋅294=86436 ≡ 101 mod 557

16: 515¹⁶=515⁸⁺⁸=515⁸⋅515⁸ ≡ 101⋅101=10201 ≡ 175 mod 557

32: 515³²=515¹⁶⁺¹⁶=515¹⁶⋅515¹⁶ ≡ 175⋅175=30625 ≡ 547 mod 557

64: 515⁶⁴=515³²⁺³²=515³²⋅515³² ≡ 547⋅547=299209 ≡ 100 mod 557

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

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

156 = 128+16+8+4

551¹⁵⁶

= 551^128+16+8+4

= 551¹²⁸⋅551¹⁶⋅551⁸⋅551⁴

≡ 352 ⋅ 160 ⋅ 157 ⋅ 581 mod 907
≡ 56320 ⋅ 157 ⋅ 581 mod 907 ≡ 86 ⋅ 157 ⋅ 581 mod 907
≡ 13502 ⋅ 581 mod 907 ≡ 804 ⋅ 581 mod 907
≡ 467124 mod 907 ≡ 19 mod 907

Es gilt also: 551¹⁵⁶ ≡ 19 mod 907

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

=>97	= 1⋅75 + 22
=>75	= 3⋅22 + 9
=>22	= 2⋅9 + 4
=>9	= 2⋅4 + 1
=>4	= 4⋅1 + 0

also gilt: ggt(97,75)=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= 9-2⋅4
4= 22-2⋅9	eingesetzt in die Zeile drüber:	1	= 1⋅9 -2⋅(22 -2⋅ 9) = 1⋅9 -2⋅22 +4⋅ 9) = -2⋅22 +5⋅ 9 (=1)
9= 75-3⋅22	eingesetzt in die Zeile drüber:	1	= -2⋅22 +5⋅(75 -3⋅ 22) = -2⋅22 +5⋅75 -15⋅ 22) = 5⋅75 -17⋅ 22 (=1)
22= 97-1⋅75	eingesetzt in die Zeile drüber:	1	= 5⋅75 -17⋅(97 -1⋅ 75) = 5⋅75 -17⋅97 +17⋅ 75) = -17⋅97 +22⋅ 75 (=1)

Es gilt also: ggt(97,75)=1 = -17⋅97 +22⋅75

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

1 +17⋅97 = +22⋅75

Es gilt also: 22⋅75 = 17⋅97 +1

Somit 22⋅75 = 1 mod 97

22 ist also das Inverse von 75 mod 97