Um längere Rechnungen zu vermeiden, rechnen wir:

(248 + 147) mod 5 ≡ (248 mod 5 + 147 mod 5) mod 5.

248 mod 5 ≡ 3 mod 5 kann man relativ leicht bestimmen, weil ja 248 = 240+8 = 5 ⋅ 48 +8.

147 mod 5 ≡ 2 mod 5 kann man relativ leicht bestimmen, weil ja 147 = 140+7 = 5 ⋅ 28 +7.

Somit gilt:

(248 + 147) mod 5 ≡ (3 + 2) mod 5 ≡ 5 mod 5 ≡ 0 mod 5.

Um längere Rechnungen zu vermeiden, rechnen wir:

(16 ⋅ 33) mod 11 ≡ (16 mod 11 ⋅ 33 mod 11) mod 11.

16 mod 11 ≡ 5 mod 11 kann man relativ leicht bestimmen, weil ja 16 = 11 + 5 = 1 ⋅ 11 + 5 ist.

33 mod 11 ≡ 0 mod 11 kann man relativ leicht bestimmen, weil ja 33 = 33 + 0 = 3 ⋅ 11 + 0 ist.

Somit gilt:

(16 ⋅ 33) mod 11 ≡ (5 ⋅ 0) mod 11 ≡ 0 mod 11.

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

2: 520²=520¹⁺¹=520¹⋅520¹ ≡ 520⋅520=270400 ≡ 551 mod 601

4: 520⁴=520²⁺²=520²⋅520² ≡ 551⋅551=303601 ≡ 96 mod 601

8: 520⁸=520⁴⁺⁴=520⁴⋅520⁴ ≡ 96⋅96=9216 ≡ 201 mod 601

16: 520¹⁶=520⁸⁺⁸=520⁸⋅520⁸ ≡ 201⋅201=40401 ≡ 134 mod 601

32: 520³²=520¹⁶⁺¹⁶=520¹⁶⋅520¹⁶ ≡ 134⋅134=17956 ≡ 527 mod 601

64: 520⁶⁴=520³²⁺³²=520³²⋅520³² ≡ 527⋅527=277729 ≡ 67 mod 601

128: 520¹²⁸=520⁶⁴⁺⁶⁴=520⁶⁴⋅520⁶⁴ ≡ 67⋅67=4489 ≡ 282 mod 601

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

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

165 = 128+32+4+1

417¹⁶⁵

= 417^128+32+4+1

= 417¹²⁸⋅417³²⋅417⁴⋅417¹

≡ 453 ⋅ 144 ⋅ 334 ⋅ 417 mod 601
≡ 65232 ⋅ 334 ⋅ 417 mod 601 ≡ 324 ⋅ 334 ⋅ 417 mod 601
≡ 108216 ⋅ 417 mod 601 ≡ 36 ⋅ 417 mod 601
≡ 15012 mod 601 ≡ 588 mod 601

Es gilt also: 417¹⁶⁵ ≡ 588 mod 601

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