Um längere Rechnungen zu vermeiden, rechnen wir:

(12000 + 23999) mod 6 ≡ (12000 mod 6 + 23999 mod 6) mod 6.

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

23999 mod 6 ≡ 5 mod 6 kann man relativ leicht bestimmen, weil ja 23999 = 24000-1 = 6 ⋅ 4000 -1 = 6 ⋅ 4000 - 6 + 5.

Somit gilt:

(12000 + 23999) mod 6 ≡ (0 + 5) mod 6 ≡ 5 mod 6.

Um längere Rechnungen zu vermeiden, rechnen wir:

(34 ⋅ 50) mod 6 ≡ (34 mod 6 ⋅ 50 mod 6) mod 6.

34 mod 6 ≡ 4 mod 6 kann man relativ leicht bestimmen, weil ja 34 = 30 + 4 = 5 ⋅ 6 + 4 ist.

50 mod 6 ≡ 2 mod 6 kann man relativ leicht bestimmen, weil ja 50 = 48 + 2 = 8 ⋅ 6 + 2 ist.

Somit gilt:

(34 ⋅ 50) mod 6 ≡ (4 ⋅ 2) mod 6 ≡ 8 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: 591¹=591

2: 591²=591¹⁺¹=591¹⋅591¹ ≡ 591⋅591=349281 ≡ 326 mod 691

4: 591⁴=591²⁺²=591²⋅591² ≡ 326⋅326=106276 ≡ 553 mod 691

8: 591⁸=591⁴⁺⁴=591⁴⋅591⁴ ≡ 553⋅553=305809 ≡ 387 mod 691

16: 591¹⁶=591⁸⁺⁸=591⁸⋅591⁸ ≡ 387⋅387=149769 ≡ 513 mod 691

32: 591³²=591¹⁶⁺¹⁶=591¹⁶⋅591¹⁶ ≡ 513⋅513=263169 ≡ 589 mod 691

64: 591⁶⁴=591³²⁺³²=591³²⋅591³² ≡ 589⋅589=346921 ≡ 39 mod 691

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

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

230 = 128+64+32+4+2

412²³⁰

= 412^{128+64+32+4+2}

= 412¹²⁸⋅412⁶⁴⋅412³²⋅412⁴⋅412²

≡ 411 ⋅ 129 ⋅ 411 ⋅ 129 ⋅ 411 mod 541
≡ 53019 ⋅ 411 ⋅ 129 ⋅ 411 mod 541 ≡ 1 ⋅ 411 ⋅ 129 ⋅ 411 mod 541
≡ 411 ⋅ 129 ⋅ 411 mod 541
≡ 53019 ⋅ 411 mod 541 ≡ 1 ⋅ 411 mod 541
≡ 411 mod 541

Es gilt also: 412²³⁰ ≡ 411 mod 541

Berechnung des größten gemeinsamen Teilers von 67 und 47

=>67	= 1⋅47 + 20
=>47	= 2⋅20 + 7
=>20	= 2⋅7 + 6
=>7	= 1⋅6 + 1
=>6	= 6⋅1 + 0

also gilt: ggt(67,47)=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= 7-1⋅6
6= 20-2⋅7	eingesetzt in die Zeile drüber:	1	= 1⋅7 -1⋅(20 -2⋅ 7) = 1⋅7 -1⋅20 +2⋅ 7) = -1⋅20 +3⋅ 7 (=1)
7= 47-2⋅20	eingesetzt in die Zeile drüber:	1	= -1⋅20 +3⋅(47 -2⋅ 20) = -1⋅20 +3⋅47 -6⋅ 20) = 3⋅47 -7⋅ 20 (=1)
20= 67-1⋅47	eingesetzt in die Zeile drüber:	1	= 3⋅47 -7⋅(67 -1⋅ 47) = 3⋅47 -7⋅67 +7⋅ 47) = -7⋅67 +10⋅ 47 (=1)

Es gilt also: ggt(67,47)=1 = -7⋅67 +10⋅47

oder wenn man -7⋅67 auf die linke Seite bringt:

1 +7⋅67 = +10⋅47

Es gilt also: 10⋅47 = 7⋅67 +1

Somit 10⋅47 = 1 mod 67

10 ist also das Inverse von 47 mod 67