Um längere Rechnungen zu vermeiden, rechnen wir:

(1201 + 5998) mod 6 ≡ (1201 mod 6 + 5998 mod 6) mod 6.

1201 mod 6 ≡ 1 mod 6 kann man relativ leicht bestimmen, weil ja 1201 = 1200+1 = 6 ⋅ 200 +1.

5998 mod 6 ≡ 4 mod 6 kann man relativ leicht bestimmen, weil ja 5998 = 6000-2 = 6 ⋅ 1000 -2 = 6 ⋅ 1000 - 6 + 4.

Somit gilt:

(1201 + 5998) mod 6 ≡ (1 + 4) mod 6 ≡ 5 mod 6.

Um längere Rechnungen zu vermeiden, rechnen wir:

(20 ⋅ 62) mod 10 ≡ (20 mod 10 ⋅ 62 mod 10) mod 10.

20 mod 10 ≡ 0 mod 10 kann man relativ leicht bestimmen, weil ja 20 = 20 + 0 = 2 ⋅ 10 + 0 ist.

62 mod 10 ≡ 2 mod 10 kann man relativ leicht bestimmen, weil ja 62 = 60 + 2 = 6 ⋅ 10 + 2 ist.

Somit gilt:

(20 ⋅ 62) mod 10 ≡ (0 ⋅ 2) mod 10 ≡ 0 mod 10.

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

2: 430²=430¹⁺¹=430¹⋅430¹ ≡ 430⋅430=184900 ≡ 477 mod 593

4: 430⁴=430²⁺²=430²⋅430² ≡ 477⋅477=227529 ≡ 410 mod 593

8: 430⁸=430⁴⁺⁴=430⁴⋅430⁴ ≡ 410⋅410=168100 ≡ 281 mod 593

16: 430¹⁶=430⁸⁺⁸=430⁸⋅430⁸ ≡ 281⋅281=78961 ≡ 92 mod 593

32: 430³²=430¹⁶⁺¹⁶=430¹⁶⋅430¹⁶ ≡ 92⋅92=8464 ≡ 162 mod 593

64: 430⁶⁴=430³²⁺³²=430³²⋅430³² ≡ 162⋅162=26244 ≡ 152 mod 593

128: 430¹²⁸=430⁶⁴⁺⁶⁴=430⁶⁴⋅430⁶⁴ ≡ 152⋅152=23104 ≡ 570 mod 593

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

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

174 = 128+32+8+4+2

237¹⁷⁴

= 237^128+32+8+4+2

= 237¹²⁸⋅237³²⋅237⁸⋅237⁴⋅237²

≡ 104 ⋅ 253 ⋅ 13 ⋅ 305 ⋅ 227 mod 337
≡ 26312 ⋅ 13 ⋅ 305 ⋅ 227 mod 337 ≡ 26 ⋅ 13 ⋅ 305 ⋅ 227 mod 337
≡ 338 ⋅ 305 ⋅ 227 mod 337 ≡ 1 ⋅ 305 ⋅ 227 mod 337
≡ 305 ⋅ 227 mod 337
≡ 69235 mod 337 ≡ 150 mod 337

Es gilt also: 237¹⁷⁴ ≡ 150 mod 337

Berechnung des größten gemeinsamen Teilers von 83 und 69

=>83	= 1⋅69 + 14
=>69	= 4⋅14 + 13
=>14	= 1⋅13 + 1
=>13	= 13⋅1 + 0

also gilt: ggt(83,69)=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= 14-1⋅13
13= 69-4⋅14	eingesetzt in die Zeile drüber:	1	= 1⋅14 -1⋅(69 -4⋅ 14) = 1⋅14 -1⋅69 +4⋅ 14) = -1⋅69 +5⋅ 14 (=1)
14= 83-1⋅69	eingesetzt in die Zeile drüber:	1	= -1⋅69 +5⋅(83 -1⋅ 69) = -1⋅69 +5⋅83 -5⋅ 69) = 5⋅83 -6⋅ 69 (=1)

Es gilt also: ggt(83,69)=1 = 5⋅83 -6⋅69

oder wenn man 5⋅83 auf die linke Seite bringt:

1 -5⋅83 = -6⋅69

-6⋅69 = -5⋅83 + 1 |+83⋅69

-6⋅69 + 83⋅69 = -5⋅83 + 83⋅69 + 1

(-6 + 83) ⋅ 69 = (-5 + 69) ⋅ 83 + 1

77⋅69 = 64⋅83 + 1

Es gilt also: 77⋅69 = 64⋅83 +1

Somit 77⋅69 = 1 mod 83

77 ist also das Inverse von 69 mod 83