Um längere Rechnungen zu vermeiden, rechnen wir:

(115 + 117) mod 6 ≡ (115 mod 6 + 117 mod 6) mod 6.

115 mod 6 ≡ 1 mod 6 kann man relativ leicht bestimmen, weil ja 115 = 120-5 = 6 ⋅ 20 -5 = 6 ⋅ 20 - 6 + 1.

117 mod 6 ≡ 3 mod 6 kann man relativ leicht bestimmen, weil ja 117 = 120-3 = 6 ⋅ 20 -3 = 6 ⋅ 20 - 6 + 3.

Somit gilt:

(115 + 117) mod 6 ≡ (1 + 3) mod 6 ≡ 4 mod 6.

Um längere Rechnungen zu vermeiden, rechnen wir:

(32 ⋅ 91) mod 3 ≡ (32 mod 3 ⋅ 91 mod 3) mod 3.

32 mod 3 ≡ 2 mod 3 kann man relativ leicht bestimmen, weil ja 32 = 30 + 2 = 10 ⋅ 3 + 2 ist.

91 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 91 = 90 + 1 = 30 ⋅ 3 + 1 ist.

Somit gilt:

(32 ⋅ 91) mod 3 ≡ (2 ⋅ 1) mod 3 ≡ 2 mod 3.

Die 128 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: 232¹=232

2: 232²=232¹⁺¹=232¹⋅232¹ ≡ 232⋅232=53824 ≡ 90 mod 401

4: 232⁴=232²⁺²=232²⋅232² ≡ 90⋅90=8100 ≡ 80 mod 401

8: 232⁸=232⁴⁺⁴=232⁴⋅232⁴ ≡ 80⋅80=6400 ≡ 385 mod 401

16: 232¹⁶=232⁸⁺⁸=232⁸⋅232⁸ ≡ 385⋅385=148225 ≡ 256 mod 401

32: 232³²=232¹⁶⁺¹⁶=232¹⁶⋅232¹⁶ ≡ 256⋅256=65536 ≡ 173 mod 401

64: 232⁶⁴=232³²⁺³²=232³²⋅232³² ≡ 173⋅173=29929 ≡ 255 mod 401

128: 232¹²⁸=232⁶⁴⁺⁶⁴=232⁶⁴⋅232⁶⁴ ≡ 255⋅255=65025 ≡ 63 mod 401

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

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

169 = 128+32+8+1

868¹⁶⁹

= 868^128+32+8+1

= 868¹²⁸⋅868³²⋅868⁸⋅868¹

≡ 266 ⋅ 426 ⋅ 189 ⋅ 868 mod 887
≡ 113316 ⋅ 189 ⋅ 868 mod 887 ≡ 667 ⋅ 189 ⋅ 868 mod 887
≡ 126063 ⋅ 868 mod 887 ≡ 109 ⋅ 868 mod 887
≡ 94612 mod 887 ≡ 590 mod 887

Es gilt also: 868¹⁶⁹ ≡ 590 mod 887

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

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

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

Es gilt also: ggt(67,20)=1 = 3⋅67 -10⋅20

oder wenn man 3⋅67 auf die linke Seite bringt:

1 -3⋅67 = -10⋅20

-10⋅20 = -3⋅67 + 1 |+67⋅20

-10⋅20 + 67⋅20 = -3⋅67 + 67⋅20 + 1

(-10 + 67) ⋅ 20 = (-3 + 20) ⋅ 67 + 1

57⋅20 = 17⋅67 + 1

Es gilt also: 57⋅20 = 17⋅67 +1

Somit 57⋅20 = 1 mod 67

57 ist also das Inverse von 20 mod 67