Um längere Rechnungen zu vermeiden, rechnen wir:

(7996 - 39) mod 4 ≡ (7996 mod 4 - 39 mod 4) mod 4.

7996 mod 4 ≡ 0 mod 4 kann man relativ leicht bestimmen, weil ja 7996 = 7000+996 = 4 ⋅ 1750 +996.

39 mod 4 ≡ 3 mod 4 kann man relativ leicht bestimmen, weil ja 39 = 40-1 = 4 ⋅ 10 -1 = 4 ⋅ 10 - 4 + 3.

Somit gilt:

(7996 - 39) mod 4 ≡ (0 - 3) mod 4 ≡ -3 mod 4 ≡ 1 mod 4.

Um längere Rechnungen zu vermeiden, rechnen wir:

(84 ⋅ 62) mod 5 ≡ (84 mod 5 ⋅ 62 mod 5) mod 5.

84 mod 5 ≡ 4 mod 5 kann man relativ leicht bestimmen, weil ja 84 = 80 + 4 = 16 ⋅ 5 + 4 ist.

62 mod 5 ≡ 2 mod 5 kann man relativ leicht bestimmen, weil ja 62 = 60 + 2 = 12 ⋅ 5 + 2 ist.

Somit gilt:

(84 ⋅ 62) mod 5 ≡ (4 ⋅ 2) mod 5 ≡ 8 mod 5 ≡ 3 mod 5.

Die 8 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: 351¹=351

2: 351²=351¹⁺¹=351¹⋅351¹ ≡ 351⋅351=123201 ≡ 447 mod 499

4: 351⁴=351²⁺²=351²⋅351² ≡ 447⋅447=199809 ≡ 209 mod 499

8: 351⁸=351⁴⁺⁴=351⁴⋅351⁴ ≡ 209⋅209=43681 ≡ 268 mod 499

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

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

238 = 128+64+32+8+4+2

409²³⁸

= 409^{128+64+32+8+4+2}

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

≡ 370 ⋅ 686 ⋅ 382 ⋅ 20 ⋅ 120 ⋅ 473 mod 719
≡ 253820 ⋅ 382 ⋅ 20 ⋅ 120 ⋅ 473 mod 719 ≡ 13 ⋅ 382 ⋅ 20 ⋅ 120 ⋅ 473 mod 719
≡ 4966 ⋅ 20 ⋅ 120 ⋅ 473 mod 719 ≡ 652 ⋅ 20 ⋅ 120 ⋅ 473 mod 719
≡ 13040 ⋅ 120 ⋅ 473 mod 719 ≡ 98 ⋅ 120 ⋅ 473 mod 719
≡ 11760 ⋅ 473 mod 719 ≡ 256 ⋅ 473 mod 719
≡ 121088 mod 719 ≡ 296 mod 719

Es gilt also: 409²³⁸ ≡ 296 mod 719

Berechnung des größten gemeinsamen Teilers von 61 und 42

=>61	= 1⋅42 + 19
=>42	= 2⋅19 + 4
=>19	= 4⋅4 + 3
=>4	= 1⋅3 + 1
=>3	= 3⋅1 + 0

also gilt: ggt(61,42)=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= 19-4⋅4	eingesetzt in die Zeile drüber:	1	= 1⋅4 -1⋅(19 -4⋅ 4) = 1⋅4 -1⋅19 +4⋅ 4) = -1⋅19 +5⋅ 4 (=1)
4= 42-2⋅19	eingesetzt in die Zeile drüber:	1	= -1⋅19 +5⋅(42 -2⋅ 19) = -1⋅19 +5⋅42 -10⋅ 19) = 5⋅42 -11⋅ 19 (=1)
19= 61-1⋅42	eingesetzt in die Zeile drüber:	1	= 5⋅42 -11⋅(61 -1⋅ 42) = 5⋅42 -11⋅61 +11⋅ 42) = -11⋅61 +16⋅ 42 (=1)

Es gilt also: ggt(61,42)=1 = -11⋅61 +16⋅42

oder wenn man -11⋅61 auf die linke Seite bringt:

1 +11⋅61 = +16⋅42

Es gilt also: 16⋅42 = 11⋅61 +1

Somit 16⋅42 = 1 mod 61

16 ist also das Inverse von 42 mod 61