Um längere Rechnungen zu vermeiden, rechnen wir:

(7998 - 20000) mod 4 ≡ (7998 mod 4 - 20000 mod 4) mod 4.

7998 mod 4 ≡ 2 mod 4 kann man relativ leicht bestimmen, weil ja 7998 = 7000+998 = 4 ⋅ 1750 +998.

20000 mod 4 ≡ 0 mod 4 kann man relativ leicht bestimmen, weil ja 20000 = 20000+0 = 4 ⋅ 5000 +0.

Somit gilt:

(7998 - 20000) mod 4 ≡ (2 - 0) mod 4 ≡ 2 mod 4.

Um längere Rechnungen zu vermeiden, rechnen wir:

(77 ⋅ 58) mod 6 ≡ (77 mod 6 ⋅ 58 mod 6) mod 6.

77 mod 6 ≡ 5 mod 6 kann man relativ leicht bestimmen, weil ja 77 = 72 + 5 = 12 ⋅ 6 + 5 ist.

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

Somit gilt:

(77 ⋅ 58) mod 6 ≡ (5 ⋅ 4) mod 6 ≡ 20 mod 6 ≡ 2 mod 6.

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

2: 172²=172¹⁺¹=172¹⋅172¹ ≡ 172⋅172=29584 ≡ 285 mod 353

4: 172⁴=172²⁺²=172²⋅172² ≡ 285⋅285=81225 ≡ 35 mod 353

8: 172⁸=172⁴⁺⁴=172⁴⋅172⁴ ≡ 35⋅35=1225 ≡ 166 mod 353

16: 172¹⁶=172⁸⁺⁸=172⁸⋅172⁸ ≡ 166⋅166=27556 ≡ 22 mod 353

32: 172³²=172¹⁶⁺¹⁶=172¹⁶⋅172¹⁶ ≡ 22⋅22=484 ≡ 131 mod 353

64: 172⁶⁴=172³²⁺³²=172³²⋅172³² ≡ 131⋅131=17161 ≡ 217 mod 353

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

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

182 = 128+32+16+4+2

350¹⁸²

= 350^{128+32+16+4+2}

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

≡ 16 ⋅ 2 ⋅ 94 ⋅ 455 ⋅ 86 mod 631
≡ 32 ⋅ 94 ⋅ 455 ⋅ 86 mod 631
≡ 3008 ⋅ 455 ⋅ 86 mod 631 ≡ 484 ⋅ 455 ⋅ 86 mod 631
≡ 220220 ⋅ 86 mod 631 ≡ 1 ⋅ 86 mod 631
≡ 86 mod 631

Es gilt also: 350¹⁸² ≡ 86 mod 631

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

=>73	= 2⋅26 + 21
=>26	= 1⋅21 + 5
=>21	= 4⋅5 + 1
=>5	= 5⋅1 + 0

also gilt: ggt(73,26)=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= 21-4⋅5
5= 26-1⋅21	eingesetzt in die Zeile drüber:	1	= 1⋅21 -4⋅(26 -1⋅ 21) = 1⋅21 -4⋅26 +4⋅ 21) = -4⋅26 +5⋅ 21 (=1)
21= 73-2⋅26	eingesetzt in die Zeile drüber:	1	= -4⋅26 +5⋅(73 -2⋅ 26) = -4⋅26 +5⋅73 -10⋅ 26) = 5⋅73 -14⋅ 26 (=1)

Es gilt also: ggt(73,26)=1 = 5⋅73 -14⋅26

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

1 -5⋅73 = -14⋅26

-14⋅26 = -5⋅73 + 1 |+73⋅26

-14⋅26 + 73⋅26 = -5⋅73 + 73⋅26 + 1

(-14 + 73) ⋅ 26 = (-5 + 26) ⋅ 73 + 1

59⋅26 = 21⋅73 + 1

Es gilt also: 59⋅26 = 21⋅73 +1

Somit 59⋅26 = 1 mod 73

59 ist also das Inverse von 26 mod 73