Um längere Rechnungen zu vermeiden, rechnen wir:

(1505 + 14997) mod 5 ≡ (1505 mod 5 + 14997 mod 5) mod 5.

1505 mod 5 ≡ 0 mod 5 kann man relativ leicht bestimmen, weil ja 1505 = 1500+5 = 5 ⋅ 300 +5.

14997 mod 5 ≡ 2 mod 5 kann man relativ leicht bestimmen, weil ja 14997 = 14000+997 = 5 ⋅ 2800 +997.

Somit gilt:

(1505 + 14997) mod 5 ≡ (0 + 2) mod 5 ≡ 2 mod 5.

Um längere Rechnungen zu vermeiden, rechnen wir:

(28 ⋅ 17) mod 10 ≡ (28 mod 10 ⋅ 17 mod 10) mod 10.

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

17 mod 10 ≡ 7 mod 10 kann man relativ leicht bestimmen, weil ja 17 = 10 + 7 = 1 ⋅ 10 + 7 ist.

Somit gilt:

(28 ⋅ 17) mod 10 ≡ (8 ⋅ 7) mod 10 ≡ 56 mod 10 ≡ 6 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: 685¹=685

2: 685²=685¹⁺¹=685¹⋅685¹ ≡ 685⋅685=469225 ≡ 349 mod 953

4: 685⁴=685²⁺²=685²⋅685² ≡ 349⋅349=121801 ≡ 770 mod 953

8: 685⁸=685⁴⁺⁴=685⁴⋅685⁴ ≡ 770⋅770=592900 ≡ 134 mod 953

16: 685¹⁶=685⁸⁺⁸=685⁸⋅685⁸ ≡ 134⋅134=17956 ≡ 802 mod 953

32: 685³²=685¹⁶⁺¹⁶=685¹⁶⋅685¹⁶ ≡ 802⋅802=643204 ≡ 882 mod 953

64: 685⁶⁴=685³²⁺³²=685³²⋅685³² ≡ 882⋅882=777924 ≡ 276 mod 953

128: 685¹²⁸=685⁶⁴⁺⁶⁴=685⁶⁴⋅685⁶⁴ ≡ 276⋅276=76176 ≡ 889 mod 953

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

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

159 = 128+16+8+4+2+1

603¹⁵⁹

= 603^{128+16+8+4+2+1}

= 603¹²⁸⋅603¹⁶⋅603⁸⋅603⁴⋅603²⋅603¹

≡ 464 ⋅ 89 ⋅ 464 ⋅ 638 ⋅ 491 ⋅ 603 mod 701
≡ 41296 ⋅ 464 ⋅ 638 ⋅ 491 ⋅ 603 mod 701 ≡ 638 ⋅ 464 ⋅ 638 ⋅ 491 ⋅ 603 mod 701
≡ 296032 ⋅ 638 ⋅ 491 ⋅ 603 mod 701 ≡ 210 ⋅ 638 ⋅ 491 ⋅ 603 mod 701
≡ 133980 ⋅ 491 ⋅ 603 mod 701 ≡ 89 ⋅ 491 ⋅ 603 mod 701
≡ 43699 ⋅ 603 mod 701 ≡ 237 ⋅ 603 mod 701
≡ 142911 mod 701 ≡ 608 mod 701

Es gilt also: 603¹⁵⁹ ≡ 608 mod 701

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

=>67	= 1⋅36 + 31
=>36	= 1⋅31 + 5
=>31	= 6⋅5 + 1
=>5	= 5⋅1 + 0

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

Es gilt also: ggt(67,36)=1 = 7⋅67 -13⋅36

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

1 -7⋅67 = -13⋅36

-13⋅36 = -7⋅67 + 1 |+67⋅36

-13⋅36 + 67⋅36 = -7⋅67 + 67⋅36 + 1

(-13 + 67) ⋅ 36 = (-7 + 36) ⋅ 67 + 1

54⋅36 = 29⋅67 + 1

Es gilt also: 54⋅36 = 29⋅67 +1

Somit 54⋅36 = 1 mod 67

54 ist also das Inverse von 36 mod 67