Um längere Rechnungen zu vermeiden, rechnen wir:

(63 + 5999) mod 3 ≡ (63 mod 3 + 5999 mod 3) mod 3.

63 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 63 = 60+3 = 3 ⋅ 20 +3.

5999 mod 3 ≡ 2 mod 3 kann man relativ leicht bestimmen, weil ja 5999 = 6000-1 = 3 ⋅ 2000 -1 = 3 ⋅ 2000 - 3 + 2.

Somit gilt:

(63 + 5999) mod 3 ≡ (0 + 2) mod 3 ≡ 2 mod 3.

Um längere Rechnungen zu vermeiden, rechnen wir:

(66 ⋅ 98) mod 5 ≡ (66 mod 5 ⋅ 98 mod 5) mod 5.

66 mod 5 ≡ 1 mod 5 kann man relativ leicht bestimmen, weil ja 66 = 65 + 1 = 13 ⋅ 5 + 1 ist.

98 mod 5 ≡ 3 mod 5 kann man relativ leicht bestimmen, weil ja 98 = 95 + 3 = 19 ⋅ 5 + 3 ist.

Somit gilt:

(66 ⋅ 98) mod 5 ≡ (1 ⋅ 3) mod 5 ≡ 3 mod 5.

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

2: 681²=681¹⁺¹=681¹⋅681¹ ≡ 681⋅681=463761 ≡ 705 mod 877

4: 681⁴=681²⁺²=681²⋅681² ≡ 705⋅705=497025 ≡ 643 mod 877

8: 681⁸=681⁴⁺⁴=681⁴⋅681⁴ ≡ 643⋅643=413449 ≡ 382 mod 877

16: 681¹⁶=681⁸⁺⁸=681⁸⋅681⁸ ≡ 382⋅382=145924 ≡ 342 mod 877

32: 681³²=681¹⁶⁺¹⁶=681¹⁶⋅681¹⁶ ≡ 342⋅342=116964 ≡ 323 mod 877

64: 681⁶⁴=681³²⁺³²=681³²⋅681³² ≡ 323⋅323=104329 ≡ 843 mod 877

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

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

209 = 128+64+16+1

266²⁰⁹

= 266^128+64+16+1

= 266¹²⁸⋅266⁶⁴⋅266¹⁶⋅266¹

≡ 326 ⋅ 202 ⋅ 6 ⋅ 266 mod 547
≡ 65852 ⋅ 6 ⋅ 266 mod 547 ≡ 212 ⋅ 6 ⋅ 266 mod 547
≡ 1272 ⋅ 266 mod 547 ≡ 178 ⋅ 266 mod 547
≡ 47348 mod 547 ≡ 306 mod 547

Es gilt also: 266²⁰⁹ ≡ 306 mod 547

Berechnung des größten gemeinsamen Teilers von 101 und 80

=>101	= 1⋅80 + 21
=>80	= 3⋅21 + 17
=>21	= 1⋅17 + 4
=>17	= 4⋅4 + 1
=>4	= 4⋅1 + 0

also gilt: ggt(101,80)=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= 17-4⋅4
4= 21-1⋅17	eingesetzt in die Zeile drüber:	1	= 1⋅17 -4⋅(21 -1⋅ 17) = 1⋅17 -4⋅21 +4⋅ 17) = -4⋅21 +5⋅ 17 (=1)
17= 80-3⋅21	eingesetzt in die Zeile drüber:	1	= -4⋅21 +5⋅(80 -3⋅ 21) = -4⋅21 +5⋅80 -15⋅ 21) = 5⋅80 -19⋅ 21 (=1)
21= 101-1⋅80	eingesetzt in die Zeile drüber:	1	= 5⋅80 -19⋅(101 -1⋅ 80) = 5⋅80 -19⋅101 +19⋅ 80) = -19⋅101 +24⋅ 80 (=1)

Es gilt also: ggt(101,80)=1 = -19⋅101 +24⋅80

oder wenn man -19⋅101 auf die linke Seite bringt:

1 +19⋅101 = +24⋅80

Es gilt also: 24⋅80 = 19⋅101 +1

Somit 24⋅80 = 1 mod 101

24 ist also das Inverse von 80 mod 101