Um längere Rechnungen zu vermeiden, rechnen wir:

(8003 - 392) mod 8 ≡ (8003 mod 8 - 392 mod 8) mod 8.

8003 mod 8 ≡ 3 mod 8 kann man relativ leicht bestimmen, weil ja 8003 = 8000+3 = 8 ⋅ 1000 +3.

392 mod 8 ≡ 0 mod 8 kann man relativ leicht bestimmen, weil ja 392 = 400-8 = 8 ⋅ 50 -8 = 8 ⋅ 50 - 8 + 0.

Somit gilt:

(8003 - 392) mod 8 ≡ (3 - 0) mod 8 ≡ 3 mod 8.

Um längere Rechnungen zu vermeiden, rechnen wir:

(46 ⋅ 56) mod 9 ≡ (46 mod 9 ⋅ 56 mod 9) mod 9.

46 mod 9 ≡ 1 mod 9 kann man relativ leicht bestimmen, weil ja 46 = 45 + 1 = 5 ⋅ 9 + 1 ist.

56 mod 9 ≡ 2 mod 9 kann man relativ leicht bestimmen, weil ja 56 = 54 + 2 = 6 ⋅ 9 + 2 ist.

Somit gilt:

(46 ⋅ 56) mod 9 ≡ (1 ⋅ 2) mod 9 ≡ 2 mod 9.

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

2: 162²=162¹⁺¹=162¹⋅162¹ ≡ 162⋅162=26244 ≡ 216 mod 241

4: 162⁴=162²⁺²=162²⋅162² ≡ 216⋅216=46656 ≡ 143 mod 241

8: 162⁸=162⁴⁺⁴=162⁴⋅162⁴ ≡ 143⋅143=20449 ≡ 205 mod 241

16: 162¹⁶=162⁸⁺⁸=162⁸⋅162⁸ ≡ 205⋅205=42025 ≡ 91 mod 241

32: 162³²=162¹⁶⁺¹⁶=162¹⁶⋅162¹⁶ ≡ 91⋅91=8281 ≡ 87 mod 241

64: 162⁶⁴=162³²⁺³²=162³²⋅162³² ≡ 87⋅87=7569 ≡ 98 mod 241

128: 162¹²⁸=162⁶⁴⁺⁶⁴=162⁶⁴⋅162⁶⁴ ≡ 98⋅98=9604 ≡ 205 mod 241

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

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

220 = 128+64+16+8+4

483²²⁰

= 483^{128+64+16+8+4}

= 483¹²⁸⋅483⁶⁴⋅483¹⁶⋅483⁸⋅483⁴

≡ 416 ⋅ 371 ⋅ 31 ⋅ 444 ⋅ 167 mod 499
≡ 154336 ⋅ 31 ⋅ 444 ⋅ 167 mod 499 ≡ 145 ⋅ 31 ⋅ 444 ⋅ 167 mod 499
≡ 4495 ⋅ 444 ⋅ 167 mod 499 ≡ 4 ⋅ 444 ⋅ 167 mod 499
≡ 1776 ⋅ 167 mod 499 ≡ 279 ⋅ 167 mod 499
≡ 46593 mod 499 ≡ 186 mod 499

Es gilt also: 483²²⁰ ≡ 186 mod 499

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

=>101	= 1⋅65 + 36
=>65	= 1⋅36 + 29
=>36	= 1⋅29 + 7
=>29	= 4⋅7 + 1
=>7	= 7⋅1 + 0

also gilt: ggt(101,65)=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= 29-4⋅7
7= 36-1⋅29	eingesetzt in die Zeile drüber:	1	= 1⋅29 -4⋅(36 -1⋅ 29) = 1⋅29 -4⋅36 +4⋅ 29) = -4⋅36 +5⋅ 29 (=1)
29= 65-1⋅36	eingesetzt in die Zeile drüber:	1	= -4⋅36 +5⋅(65 -1⋅ 36) = -4⋅36 +5⋅65 -5⋅ 36) = 5⋅65 -9⋅ 36 (=1)
36= 101-1⋅65	eingesetzt in die Zeile drüber:	1	= 5⋅65 -9⋅(101 -1⋅ 65) = 5⋅65 -9⋅101 +9⋅ 65) = -9⋅101 +14⋅ 65 (=1)

Es gilt also: ggt(101,65)=1 = -9⋅101 +14⋅65

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

1 +9⋅101 = +14⋅65

Es gilt also: 14⋅65 = 9⋅101 +1

Somit 14⋅65 = 1 mod 101

14 ist also das Inverse von 65 mod 101