Um längere Rechnungen zu vermeiden, rechnen wir:

(5994 + 23996) mod 6 ≡ (5994 mod 6 + 23996 mod 6) mod 6.

5994 mod 6 ≡ 0 mod 6 kann man relativ leicht bestimmen, weil ja 5994 = 6000-6 = 6 ⋅ 1000 -6 = 6 ⋅ 1000 - 6 + 0.

23996 mod 6 ≡ 2 mod 6 kann man relativ leicht bestimmen, weil ja 23996 = 24000-4 = 6 ⋅ 4000 -4 = 6 ⋅ 4000 - 6 + 2.

Somit gilt:

(5994 + 23996) mod 6 ≡ (0 + 2) mod 6 ≡ 2 mod 6.

Um längere Rechnungen zu vermeiden, rechnen wir:

(62 ⋅ 82) mod 9 ≡ (62 mod 9 ⋅ 82 mod 9) mod 9.

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

82 mod 9 ≡ 1 mod 9 kann man relativ leicht bestimmen, weil ja 82 = 81 + 1 = 9 ⋅ 9 + 1 ist.

Somit gilt:

(62 ⋅ 82) mod 9 ≡ (8 ⋅ 1) mod 9 ≡ 8 mod 9.

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

2: 554²=554¹⁺¹=554¹⋅554¹ ≡ 554⋅554=306916 ≡ 71 mod 797

4: 554⁴=554²⁺²=554²⋅554² ≡ 71⋅71=5041 ≡ 259 mod 797

8: 554⁸=554⁴⁺⁴=554⁴⋅554⁴ ≡ 259⋅259=67081 ≡ 133 mod 797

16: 554¹⁶=554⁸⁺⁸=554⁸⋅554⁸ ≡ 133⋅133=17689 ≡ 155 mod 797

32: 554³²=554¹⁶⁺¹⁶=554¹⁶⋅554¹⁶ ≡ 155⋅155=24025 ≡ 115 mod 797

64: 554⁶⁴=554³²⁺³²=554³²⋅554³² ≡ 115⋅115=13225 ≡ 473 mod 797

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

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

79 = 64+8+4+2+1

336⁷⁹

= 336^64+8+4+2+1

= 336⁶⁴⋅336⁸⋅336⁴⋅336²⋅336¹

≡ 16 ⋅ 347 ⋅ 289 ⋅ 17 ⋅ 336 mod 457
≡ 5552 ⋅ 289 ⋅ 17 ⋅ 336 mod 457 ≡ 68 ⋅ 289 ⋅ 17 ⋅ 336 mod 457
≡ 19652 ⋅ 17 ⋅ 336 mod 457 ≡ 1 ⋅ 17 ⋅ 336 mod 457
≡ 17 ⋅ 336 mod 457
≡ 5712 mod 457 ≡ 228 mod 457

Es gilt also: 336⁷⁹ ≡ 228 mod 457

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