Um längere Rechnungen zu vermeiden, rechnen wir:

(8008 - 326) mod 8 ≡ (8008 mod 8 - 326 mod 8) mod 8.

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

326 mod 8 ≡ 6 mod 8 kann man relativ leicht bestimmen, weil ja 326 = 320+6 = 8 ⋅ 40 +6.

Somit gilt:

(8008 - 326) mod 8 ≡ (0 - 6) mod 8 ≡ -6 mod 8 ≡ 2 mod 8.

Um längere Rechnungen zu vermeiden, rechnen wir:

(84 ⋅ 91) mod 3 ≡ (84 mod 3 ⋅ 91 mod 3) mod 3.

84 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 84 = 84 + 0 = 28 ⋅ 3 + 0 ist.

91 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 91 = 90 + 1 = 30 ⋅ 3 + 1 ist.

Somit gilt:

(84 ⋅ 91) mod 3 ≡ (0 ⋅ 1) mod 3 ≡ 0 mod 3.

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

2: 633²=633¹⁺¹=633¹⋅633¹ ≡ 633⋅633=400689 ≡ 595 mod 797

4: 633⁴=633²⁺²=633²⋅633² ≡ 595⋅595=354025 ≡ 157 mod 797

8: 633⁸=633⁴⁺⁴=633⁴⋅633⁴ ≡ 157⋅157=24649 ≡ 739 mod 797

16: 633¹⁶=633⁸⁺⁸=633⁸⋅633⁸ ≡ 739⋅739=546121 ≡ 176 mod 797

32: 633³²=633¹⁶⁺¹⁶=633¹⁶⋅633¹⁶ ≡ 176⋅176=30976 ≡ 690 mod 797

64: 633⁶⁴=633³²⁺³²=633³²⋅633³² ≡ 690⋅690=476100 ≡ 291 mod 797

128: 633¹²⁸=633⁶⁴⁺⁶⁴=633⁶⁴⋅633⁶⁴ ≡ 291⋅291=84681 ≡ 199 mod 797

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

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

61 = 32+16+8+4+1

475⁶¹

= 475^32+16+8+4+1

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

≡ 429 ⋅ 263 ⋅ 279 ⋅ 233 ⋅ 475 mod 491
≡ 112827 ⋅ 279 ⋅ 233 ⋅ 475 mod 491 ≡ 388 ⋅ 279 ⋅ 233 ⋅ 475 mod 491
≡ 108252 ⋅ 233 ⋅ 475 mod 491 ≡ 232 ⋅ 233 ⋅ 475 mod 491
≡ 54056 ⋅ 475 mod 491 ≡ 46 ⋅ 475 mod 491
≡ 21850 mod 491 ≡ 246 mod 491

Es gilt also: 475⁶¹ ≡ 246 mod 491

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

=>73	= 3⋅23 + 4
=>23	= 5⋅4 + 3
=>4	= 1⋅3 + 1
=>3	= 3⋅1 + 0

also gilt: ggt(73,23)=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= 4-1⋅3
3= 23-5⋅4	eingesetzt in die Zeile drüber:	1	= 1⋅4 -1⋅(23 -5⋅ 4) = 1⋅4 -1⋅23 +5⋅ 4) = -1⋅23 +6⋅ 4 (=1)
4= 73-3⋅23	eingesetzt in die Zeile drüber:	1	= -1⋅23 +6⋅(73 -3⋅ 23) = -1⋅23 +6⋅73 -18⋅ 23) = 6⋅73 -19⋅ 23 (=1)

Es gilt also: ggt(73,23)=1 = 6⋅73 -19⋅23

oder wenn man 6⋅73 auf die linke Seite bringt:

1 -6⋅73 = -19⋅23

-19⋅23 = -6⋅73 + 1 |+73⋅23

-19⋅23 + 73⋅23 = -6⋅73 + 73⋅23 + 1

(-19 + 73) ⋅ 23 = (-6 + 23) ⋅ 73 + 1

54⋅23 = 17⋅73 + 1

Es gilt also: 54⋅23 = 17⋅73 +1

Somit 54⋅23 = 1 mod 73

54 ist also das Inverse von 23 mod 73