Um längere Rechnungen zu vermeiden, rechnen wir:

(75 + 2392) mod 8 ≡ (75 mod 8 + 2392 mod 8) mod 8.

75 mod 8 ≡ 3 mod 8 kann man relativ leicht bestimmen, weil ja 75 = 80-5 = 8 ⋅ 10 -5 = 8 ⋅ 10 - 8 + 3.

2392 mod 8 ≡ 0 mod 8 kann man relativ leicht bestimmen, weil ja 2392 = 2400-8 = 8 ⋅ 300 -8 = 8 ⋅ 300 - 8 + 0.

Somit gilt:

(75 + 2392) mod 8 ≡ (3 + 0) mod 8 ≡ 3 mod 8.

Um längere Rechnungen zu vermeiden, rechnen wir:

(92 ⋅ 19) mod 8 ≡ (92 mod 8 ⋅ 19 mod 8) mod 8.

92 mod 8 ≡ 4 mod 8 kann man relativ leicht bestimmen, weil ja 92 = 88 + 4 = 11 ⋅ 8 + 4 ist.

19 mod 8 ≡ 3 mod 8 kann man relativ leicht bestimmen, weil ja 19 = 16 + 3 = 2 ⋅ 8 + 3 ist.

Somit gilt:

(92 ⋅ 19) mod 8 ≡ (4 ⋅ 3) mod 8 ≡ 12 mod 8 ≡ 4 mod 8.

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

2: 387²=387¹⁺¹=387¹⋅387¹ ≡ 387⋅387=149769 ≡ 384 mod 433

4: 387⁴=387²⁺²=387²⋅387² ≡ 384⋅384=147456 ≡ 236 mod 433

8: 387⁸=387⁴⁺⁴=387⁴⋅387⁴ ≡ 236⋅236=55696 ≡ 272 mod 433

16: 387¹⁶=387⁸⁺⁸=387⁸⋅387⁸ ≡ 272⋅272=73984 ≡ 374 mod 433

32: 387³²=387¹⁶⁺¹⁶=387¹⁶⋅387¹⁶ ≡ 374⋅374=139876 ≡ 17 mod 433

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

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

230 = 128+64+32+4+2

222²³⁰

= 222^{128+64+32+4+2}

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

≡ 15 ⋅ 225 ⋅ 15 ⋅ 181 ⋅ 120 mod 241
≡ 3375 ⋅ 15 ⋅ 181 ⋅ 120 mod 241 ≡ 1 ⋅ 15 ⋅ 181 ⋅ 120 mod 241
≡ 15 ⋅ 181 ⋅ 120 mod 241
≡ 2715 ⋅ 120 mod 241 ≡ 64 ⋅ 120 mod 241
≡ 7680 mod 241 ≡ 209 mod 241

Es gilt also: 222²³⁰ ≡ 209 mod 241

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

=>101	= 1⋅80 + 21
=>80	= 3⋅21 + 17
=>21	= 1⋅17 + 4
=>17	= 4⋅4 + 1
=>4	= 4⋅1 + 0

also gilt: ggt(101,80)=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-4⋅4
4= 21-1⋅17	eingesetzt in die Zeile drüber:	1	= 1⋅17 -4⋅(21 -1⋅ 17) = 1⋅17 -4⋅21 +4⋅ 17) = -4⋅21 +5⋅ 17 (=1)
17= 80-3⋅21	eingesetzt in die Zeile drüber:	1	= -4⋅21 +5⋅(80 -3⋅ 21) = -4⋅21 +5⋅80 -15⋅ 21) = 5⋅80 -19⋅ 21 (=1)
21= 101-1⋅80	eingesetzt in die Zeile drüber:	1	= 5⋅80 -19⋅(101 -1⋅ 80) = 5⋅80 -19⋅101 +19⋅ 80) = -19⋅101 +24⋅ 80 (=1)

Es gilt also: ggt(101,80)=1 = -19⋅101 +24⋅80

oder wenn man -19⋅101 auf die linke Seite bringt:

1 +19⋅101 = +24⋅80

Es gilt also: 24⋅80 = 19⋅101 +1

Somit 24⋅80 = 1 mod 101

24 ist also das Inverse von 80 mod 101