Um längere Rechnungen zu vermeiden, rechnen wir:

(1996 - 5001) mod 5 ≡ (1996 mod 5 - 5001 mod 5) mod 5.

1996 mod 5 ≡ 1 mod 5 kann man relativ leicht bestimmen, weil ja 1996 = 1900+96 = 5 ⋅ 380 +96.

5001 mod 5 ≡ 1 mod 5 kann man relativ leicht bestimmen, weil ja 5001 = 5000+1 = 5 ⋅ 1000 +1.

Somit gilt:

(1996 - 5001) mod 5 ≡ (1 - 1) mod 5 ≡ 0 mod 5.

Um längere Rechnungen zu vermeiden, rechnen wir:

(18 ⋅ 69) mod 10 ≡ (18 mod 10 ⋅ 69 mod 10) mod 10.

18 mod 10 ≡ 8 mod 10 kann man relativ leicht bestimmen, weil ja 18 = 10 + 8 = 1 ⋅ 10 + 8 ist.

69 mod 10 ≡ 9 mod 10 kann man relativ leicht bestimmen, weil ja 69 = 60 + 9 = 6 ⋅ 10 + 9 ist.

Somit gilt:

(18 ⋅ 69) mod 10 ≡ (8 ⋅ 9) mod 10 ≡ 72 mod 10 ≡ 2 mod 10.

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

2: 223²=223¹⁺¹=223¹⋅223¹ ≡ 223⋅223=49729 ≡ 240 mod 409

4: 223⁴=223²⁺²=223²⋅223² ≡ 240⋅240=57600 ≡ 340 mod 409

8: 223⁸=223⁴⁺⁴=223⁴⋅223⁴ ≡ 340⋅340=115600 ≡ 262 mod 409

16: 223¹⁶=223⁸⁺⁸=223⁸⋅223⁸ ≡ 262⋅262=68644 ≡ 341 mod 409

32: 223³²=223¹⁶⁺¹⁶=223¹⁶⋅223¹⁶ ≡ 341⋅341=116281 ≡ 125 mod 409

64: 223⁶⁴=223³²⁺³²=223³²⋅223³² ≡ 125⋅125=15625 ≡ 83 mod 409

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

834⁷⁹

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

= 834⁶⁴⋅834⁸⋅834⁴⋅834²⋅834¹

≡ 677 ⋅ 707 ⋅ 616 ⋅ 148 ⋅ 834 mod 887
≡ 478639 ⋅ 616 ⋅ 148 ⋅ 834 mod 887 ≡ 546 ⋅ 616 ⋅ 148 ⋅ 834 mod 887
≡ 336336 ⋅ 148 ⋅ 834 mod 887 ≡ 163 ⋅ 148 ⋅ 834 mod 887
≡ 24124 ⋅ 834 mod 887 ≡ 175 ⋅ 834 mod 887
≡ 145950 mod 887 ≡ 482 mod 887

Es gilt also: 834⁷⁹ ≡ 482 mod 887

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

=>73	= 2⋅33 + 7
=>33	= 4⋅7 + 5
=>7	= 1⋅5 + 2
=>5	= 2⋅2 + 1
=>2	= 2⋅1 + 0

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

Es gilt also: ggt(73,33)=1 = -14⋅73 +31⋅33

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

1 +14⋅73 = +31⋅33

Es gilt also: 31⋅33 = 14⋅73 +1

Somit 31⋅33 = 1 mod 73

31 ist also das Inverse von 33 mod 73