Um längere Rechnungen zu vermeiden, rechnen wir:

(1802 + 1200) mod 6 ≡ (1802 mod 6 + 1200 mod 6) mod 6.

1802 mod 6 ≡ 2 mod 6 kann man relativ leicht bestimmen, weil ja 1802 = 1800+2 = 6 ⋅ 300 +2.

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

Somit gilt:

(1802 + 1200) mod 6 ≡ (2 + 0) mod 6 ≡ 2 mod 6.

Um längere Rechnungen zu vermeiden, rechnen wir:

(66 ⋅ 95) mod 6 ≡ (66 mod 6 ⋅ 95 mod 6) mod 6.

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

95 mod 6 ≡ 5 mod 6 kann man relativ leicht bestimmen, weil ja 95 = 90 + 5 = 15 ⋅ 6 + 5 ist.

Somit gilt:

(66 ⋅ 95) mod 6 ≡ (0 ⋅ 5) mod 6 ≡ 0 mod 6.

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

2: 212²=212¹⁺¹=212¹⋅212¹ ≡ 212⋅212=44944 ≡ 60 mod 229

4: 212⁴=212²⁺²=212²⋅212² ≡ 60⋅60=3600 ≡ 165 mod 229

8: 212⁸=212⁴⁺⁴=212⁴⋅212⁴ ≡ 165⋅165=27225 ≡ 203 mod 229

16: 212¹⁶=212⁸⁺⁸=212⁸⋅212⁸ ≡ 203⋅203=41209 ≡ 218 mod 229

32: 212³²=212¹⁶⁺¹⁶=212¹⁶⋅212¹⁶ ≡ 218⋅218=47524 ≡ 121 mod 229

64: 212⁶⁴=212³²⁺³²=212³²⋅212³² ≡ 121⋅121=14641 ≡ 214 mod 229

128: 212¹²⁸=212⁶⁴⁺⁶⁴=212⁶⁴⋅212⁶⁴ ≡ 214⋅214=45796 ≡ 225 mod 229

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

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

213 = 128+64+16+4+1

245²¹³

= 245^{128+64+16+4+1}

= 245¹²⁸⋅245⁶⁴⋅245¹⁶⋅245⁴⋅245¹

≡ 256 ⋅ 16 ⋅ 2 ⋅ 216 ⋅ 245 mod 601
≡ 4096 ⋅ 2 ⋅ 216 ⋅ 245 mod 601 ≡ 490 ⋅ 2 ⋅ 216 ⋅ 245 mod 601
≡ 980 ⋅ 216 ⋅ 245 mod 601 ≡ 379 ⋅ 216 ⋅ 245 mod 601
≡ 81864 ⋅ 245 mod 601 ≡ 128 ⋅ 245 mod 601
≡ 31360 mod 601 ≡ 108 mod 601

Es gilt also: 245²¹³ ≡ 108 mod 601

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

=>83	= 2⋅29 + 25
=>29	= 1⋅25 + 4
=>25	= 6⋅4 + 1
=>4	= 4⋅1 + 0

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

Es gilt also: ggt(83,29)=1 = 7⋅83 -20⋅29

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

1 -7⋅83 = -20⋅29

-20⋅29 = -7⋅83 + 1 |+83⋅29

-20⋅29 + 83⋅29 = -7⋅83 + 83⋅29 + 1

(-20 + 83) ⋅ 29 = (-7 + 29) ⋅ 83 + 1

63⋅29 = 22⋅83 + 1

Es gilt also: 63⋅29 = 22⋅83 +1

Somit 63⋅29 = 1 mod 83

63 ist also das Inverse von 29 mod 83