Um längere Rechnungen zu vermeiden, rechnen wir:

(995 + 150) mod 5 ≡ (995 mod 5 + 150 mod 5) mod 5.

995 mod 5 ≡ 0 mod 5 kann man relativ leicht bestimmen, weil ja 995 = 900+95 = 5 ⋅ 180 +95.

150 mod 5 ≡ 0 mod 5 kann man relativ leicht bestimmen, weil ja 150 = 150+0 = 5 ⋅ 30 +0.

Somit gilt:

(995 + 150) mod 5 ≡ (0 + 0) mod 5 ≡ 0 mod 5.

Um längere Rechnungen zu vermeiden, rechnen wir:

(60 ⋅ 67) mod 5 ≡ (60 mod 5 ⋅ 67 mod 5) mod 5.

60 mod 5 ≡ 0 mod 5 kann man relativ leicht bestimmen, weil ja 60 = 60 + 0 = 12 ⋅ 5 + 0 ist.

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

Somit gilt:

(60 ⋅ 67) mod 5 ≡ (0 ⋅ 2) mod 5 ≡ 0 mod 5.

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

2: 402²=402¹⁺¹=402¹⋅402¹ ≡ 402⋅402=161604 ≡ 601 mod 691

4: 402⁴=402²⁺²=402²⋅402² ≡ 601⋅601=361201 ≡ 499 mod 691

8: 402⁸=402⁴⁺⁴=402⁴⋅402⁴ ≡ 499⋅499=249001 ≡ 241 mod 691

16: 402¹⁶=402⁸⁺⁸=402⁸⋅402⁸ ≡ 241⋅241=58081 ≡ 37 mod 691

32: 402³²=402¹⁶⁺¹⁶=402¹⁶⋅402¹⁶ ≡ 37⋅37=1369 ≡ 678 mod 691

64: 402⁶⁴=402³²⁺³²=402³²⋅402³² ≡ 678⋅678=459684 ≡ 169 mod 691

128: 402¹²⁸=402⁶⁴⁺⁶⁴=402⁶⁴⋅402⁶⁴ ≡ 169⋅169=28561 ≡ 230 mod 691

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

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

178 = 128+32+16+2

341¹⁷⁸

= 341^128+32+16+2

= 341¹²⁸⋅341³²⋅341¹⁶⋅341²

≡ 54 ⋅ 305 ⋅ 456 ⋅ 175 mod 523
≡ 16470 ⋅ 456 ⋅ 175 mod 523 ≡ 257 ⋅ 456 ⋅ 175 mod 523
≡ 117192 ⋅ 175 mod 523 ≡ 40 ⋅ 175 mod 523
≡ 7000 mod 523 ≡ 201 mod 523

Es gilt also: 341¹⁷⁸ ≡ 201 mod 523

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

=>101	= 1⋅65 + 36
=>65	= 1⋅36 + 29
=>36	= 1⋅29 + 7
=>29	= 4⋅7 + 1
=>7	= 7⋅1 + 0

also gilt: ggt(101,65)=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= 29-4⋅7
7= 36-1⋅29	eingesetzt in die Zeile drüber:	1	= 1⋅29 -4⋅(36 -1⋅ 29) = 1⋅29 -4⋅36 +4⋅ 29) = -4⋅36 +5⋅ 29 (=1)
29= 65-1⋅36	eingesetzt in die Zeile drüber:	1	= -4⋅36 +5⋅(65 -1⋅ 36) = -4⋅36 +5⋅65 -5⋅ 36) = 5⋅65 -9⋅ 36 (=1)
36= 101-1⋅65	eingesetzt in die Zeile drüber:	1	= 5⋅65 -9⋅(101 -1⋅ 65) = 5⋅65 -9⋅101 +9⋅ 65) = -9⋅101 +14⋅ 65 (=1)

Es gilt also: ggt(101,65)=1 = -9⋅101 +14⋅65

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

1 +9⋅101 = +14⋅65

Es gilt also: 14⋅65 = 9⋅101 +1

Somit 14⋅65 = 1 mod 101

14 ist also das Inverse von 65 mod 101