Um längere Rechnungen zu vermeiden, rechnen wir:

(452 + 18003) mod 9 ≡ (452 mod 9 + 18003 mod 9) mod 9.

452 mod 9 ≡ 2 mod 9 kann man relativ leicht bestimmen, weil ja 452 = 450+2 = 9 ⋅ 50 +2.

18003 mod 9 ≡ 3 mod 9 kann man relativ leicht bestimmen, weil ja 18003 = 18000+3 = 9 ⋅ 2000 +3.

Somit gilt:

(452 + 18003) mod 9 ≡ (2 + 3) mod 9 ≡ 5 mod 9.

Um längere Rechnungen zu vermeiden, rechnen wir:

(74 ⋅ 49) mod 3 ≡ (74 mod 3 ⋅ 49 mod 3) mod 3.

74 mod 3 ≡ 2 mod 3 kann man relativ leicht bestimmen, weil ja 74 = 72 + 2 = 24 ⋅ 3 + 2 ist.

49 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 49 = 48 + 1 = 16 ⋅ 3 + 1 ist.

Somit gilt:

(74 ⋅ 49) mod 3 ≡ (2 ⋅ 1) mod 3 ≡ 2 mod 3.

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

2: 243²=243¹⁺¹=243¹⋅243¹ ≡ 243⋅243=59049 ≡ 310 mod 389

4: 243⁴=243²⁺²=243²⋅243² ≡ 310⋅310=96100 ≡ 17 mod 389

8: 243⁸=243⁴⁺⁴=243⁴⋅243⁴ ≡ 17⋅17=289 ≡ 289 mod 389

16: 243¹⁶=243⁸⁺⁸=243⁸⋅243⁸ ≡ 289⋅289=83521 ≡ 275 mod 389

32: 243³²=243¹⁶⁺¹⁶=243¹⁶⋅243¹⁶ ≡ 275⋅275=75625 ≡ 159 mod 389

64: 243⁶⁴=243³²⁺³²=243³²⋅243³² ≡ 159⋅159=25281 ≡ 385 mod 389

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

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

159 = 128+16+8+4+2+1

489¹⁵⁹

= 489^{128+16+8+4+2+1}

= 489¹²⁸⋅489¹⁶⋅489⁸⋅489⁴⋅489²⋅489¹

≡ 175 ⋅ 239 ⋅ 278 ⋅ 778 ⋅ 687 ⋅ 489 mod 811
≡ 41825 ⋅ 278 ⋅ 778 ⋅ 687 ⋅ 489 mod 811 ≡ 464 ⋅ 278 ⋅ 778 ⋅ 687 ⋅ 489 mod 811
≡ 128992 ⋅ 778 ⋅ 687 ⋅ 489 mod 811 ≡ 43 ⋅ 778 ⋅ 687 ⋅ 489 mod 811
≡ 33454 ⋅ 687 ⋅ 489 mod 811 ≡ 203 ⋅ 687 ⋅ 489 mod 811
≡ 139461 ⋅ 489 mod 811 ≡ 780 ⋅ 489 mod 811
≡ 381420 mod 811 ≡ 250 mod 811

Es gilt also: 489¹⁵⁹ ≡ 250 mod 811

Berechnung des größten gemeinsamen Teilers von 73 und 32

=>73	= 2⋅32 + 9
=>32	= 3⋅9 + 5
=>9	= 1⋅5 + 4
=>5	= 1⋅4 + 1
=>4	= 4⋅1 + 0

also gilt: ggt(73,32)=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= 5-1⋅4
4= 9-1⋅5	eingesetzt in die Zeile drüber:	1	= 1⋅5 -1⋅(9 -1⋅ 5) = 1⋅5 -1⋅9 +1⋅ 5) = -1⋅9 +2⋅ 5 (=1)
5= 32-3⋅9	eingesetzt in die Zeile drüber:	1	= -1⋅9 +2⋅(32 -3⋅ 9) = -1⋅9 +2⋅32 -6⋅ 9) = 2⋅32 -7⋅ 9 (=1)
9= 73-2⋅32	eingesetzt in die Zeile drüber:	1	= 2⋅32 -7⋅(73 -2⋅ 32) = 2⋅32 -7⋅73 +14⋅ 32) = -7⋅73 +16⋅ 32 (=1)

Es gilt also: ggt(73,32)=1 = -7⋅73 +16⋅32

oder wenn man -7⋅73 auf die linke Seite bringt:

1 +7⋅73 = +16⋅32

Es gilt also: 16⋅32 = 7⋅73 +1

Somit 16⋅32 = 1 mod 73

16 ist also das Inverse von 32 mod 73