Um längere Rechnungen zu vermeiden, rechnen wir:

(174 - 11997) mod 6 ≡ (174 mod 6 - 11997 mod 6) mod 6.

174 mod 6 ≡ 0 mod 6 kann man relativ leicht bestimmen, weil ja 174 = 180-6 = 6 ⋅ 30 -6 = 6 ⋅ 30 - 6 + 0.

11997 mod 6 ≡ 3 mod 6 kann man relativ leicht bestimmen, weil ja 11997 = 12000-3 = 6 ⋅ 2000 -3 = 6 ⋅ 2000 - 6 + 3.

Somit gilt:

(174 - 11997) mod 6 ≡ (0 - 3) mod 6 ≡ -3 mod 6 ≡ 3 mod 6.

Um längere Rechnungen zu vermeiden, rechnen wir:

(17 ⋅ 83) mod 5 ≡ (17 mod 5 ⋅ 83 mod 5) mod 5.

17 mod 5 ≡ 2 mod 5 kann man relativ leicht bestimmen, weil ja 17 = 15 + 2 = 3 ⋅ 5 + 2 ist.

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

Somit gilt:

(17 ⋅ 83) mod 5 ≡ (2 ⋅ 3) mod 5 ≡ 6 mod 5 ≡ 1 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: 317¹=317

2: 317²=317¹⁺¹=317¹⋅317¹ ≡ 317⋅317=100489 ≡ 180 mod 829

4: 317⁴=317²⁺²=317²⋅317² ≡ 180⋅180=32400 ≡ 69 mod 829

8: 317⁸=317⁴⁺⁴=317⁴⋅317⁴ ≡ 69⋅69=4761 ≡ 616 mod 829

16: 317¹⁶=317⁸⁺⁸=317⁸⋅317⁸ ≡ 616⋅616=379456 ≡ 603 mod 829

32: 317³²=317¹⁶⁺¹⁶=317¹⁶⋅317¹⁶ ≡ 603⋅603=363609 ≡ 507 mod 829

64: 317⁶⁴=317³²⁺³²=317³²⋅317³² ≡ 507⋅507=257049 ≡ 59 mod 829

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

402²⁰⁹

= 402^128+64+16+1

= 402¹²⁸⋅402⁶⁴⋅402¹⁶⋅402¹

≡ 617 ⋅ 331 ⋅ 600 ⋅ 402 mod 619
≡ 204227 ⋅ 600 ⋅ 402 mod 619 ≡ 576 ⋅ 600 ⋅ 402 mod 619
≡ 345600 ⋅ 402 mod 619 ≡ 198 ⋅ 402 mod 619
≡ 79596 mod 619 ≡ 364 mod 619

Es gilt also: 402²⁰⁹ ≡ 364 mod 619

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

=>73	= 1⋅48 + 25
=>48	= 1⋅25 + 23
=>25	= 1⋅23 + 2
=>23	= 11⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(73,48)=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= 23-11⋅2
2= 25-1⋅23	eingesetzt in die Zeile drüber:	1	= 1⋅23 -11⋅(25 -1⋅ 23) = 1⋅23 -11⋅25 +11⋅ 23) = -11⋅25 +12⋅ 23 (=1)
23= 48-1⋅25	eingesetzt in die Zeile drüber:	1	= -11⋅25 +12⋅(48 -1⋅ 25) = -11⋅25 +12⋅48 -12⋅ 25) = 12⋅48 -23⋅ 25 (=1)
25= 73-1⋅48	eingesetzt in die Zeile drüber:	1	= 12⋅48 -23⋅(73 -1⋅ 48) = 12⋅48 -23⋅73 +23⋅ 48) = -23⋅73 +35⋅ 48 (=1)

Es gilt also: ggt(73,48)=1 = -23⋅73 +35⋅48

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

1 +23⋅73 = +35⋅48

Es gilt also: 35⋅48 = 23⋅73 +1

Somit 35⋅48 = 1 mod 73

35 ist also das Inverse von 48 mod 73