Um längere Rechnungen zu vermeiden, rechnen wir:

(31995 - 7999) mod 8 ≡ (31995 mod 8 - 7999 mod 8) mod 8.

31995 mod 8 ≡ 3 mod 8 kann man relativ leicht bestimmen, weil ja 31995 = 31000+995 = 8 ⋅ 3875 +995.

7999 mod 8 ≡ 7 mod 8 kann man relativ leicht bestimmen, weil ja 7999 = 7000+999 = 8 ⋅ 875 +999.

Somit gilt:

(31995 - 7999) mod 8 ≡ (3 - 7) mod 8 ≡ -4 mod 8 ≡ 4 mod 8.

Um längere Rechnungen zu vermeiden, rechnen wir:

(74 ⋅ 79) mod 6 ≡ (74 mod 6 ⋅ 79 mod 6) mod 6.

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

79 mod 6 ≡ 1 mod 6 kann man relativ leicht bestimmen, weil ja 79 = 78 + 1 = 13 ⋅ 6 + 1 ist.

Somit gilt:

(74 ⋅ 79) mod 6 ≡ (2 ⋅ 1) 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: 193¹=193

2: 193²=193¹⁺¹=193¹⋅193¹ ≡ 193⋅193=37249 ≡ 202 mod 233

4: 193⁴=193²⁺²=193²⋅193² ≡ 202⋅202=40804 ≡ 29 mod 233

8: 193⁸=193⁴⁺⁴=193⁴⋅193⁴ ≡ 29⋅29=841 ≡ 142 mod 233

16: 193¹⁶=193⁸⁺⁸=193⁸⋅193⁸ ≡ 142⋅142=20164 ≡ 126 mod 233

32: 193³²=193¹⁶⁺¹⁶=193¹⁶⋅193¹⁶ ≡ 126⋅126=15876 ≡ 32 mod 233

64: 193⁶⁴=193³²⁺³²=193³²⋅193³² ≡ 32⋅32=1024 ≡ 92 mod 233

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

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

201 = 128+64+8+1

523²⁰¹

= 523^128+64+8+1

= 523¹²⁸⋅523⁶⁴⋅523⁸⋅523¹

≡ 260 ⋅ 332 ⋅ 283 ⋅ 523 mod 743
≡ 86320 ⋅ 283 ⋅ 523 mod 743 ≡ 132 ⋅ 283 ⋅ 523 mod 743
≡ 37356 ⋅ 523 mod 743 ≡ 206 ⋅ 523 mod 743
≡ 107738 mod 743 ≡ 3 mod 743

Es gilt also: 523²⁰¹ ≡ 3 mod 743

Berechnung des größten gemeinsamen Teilers von 59 und 50

=>59	= 1⋅50 + 9
=>50	= 5⋅9 + 5
=>9	= 1⋅5 + 4
=>5	= 1⋅4 + 1
=>4	= 4⋅1 + 0

also gilt: ggt(59,50)=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-1⋅4
4= 9-1⋅5	eingesetzt in die Zeile drüber:	1	= 1⋅5 -1⋅(9 -1⋅ 5) = 1⋅5 -1⋅9 +1⋅ 5) = -1⋅9 +2⋅ 5 (=1)
5= 50-5⋅9	eingesetzt in die Zeile drüber:	1	= -1⋅9 +2⋅(50 -5⋅ 9) = -1⋅9 +2⋅50 -10⋅ 9) = 2⋅50 -11⋅ 9 (=1)
9= 59-1⋅50	eingesetzt in die Zeile drüber:	1	= 2⋅50 -11⋅(59 -1⋅ 50) = 2⋅50 -11⋅59 +11⋅ 50) = -11⋅59 +13⋅ 50 (=1)

Es gilt also: ggt(59,50)=1 = -11⋅59 +13⋅50

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

1 +11⋅59 = +13⋅50

Es gilt also: 13⋅50 = 11⋅59 +1

Somit 13⋅50 = 1 mod 59

13 ist also das Inverse von 50 mod 59