Um längere Rechnungen zu vermeiden, rechnen wir:

(3000 - 120) mod 3 ≡ (3000 mod 3 - 120 mod 3) mod 3.

3000 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 3000 = 3000+0 = 3 ⋅ 1000 +0.

120 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 120 = 120+0 = 3 ⋅ 40 +0.

Somit gilt:

(3000 - 120) mod 3 ≡ (0 - 0) mod 3 ≡ 0 mod 3.

Um längere Rechnungen zu vermeiden, rechnen wir:

(73 ⋅ 97) mod 10 ≡ (73 mod 10 ⋅ 97 mod 10) mod 10.

73 mod 10 ≡ 3 mod 10 kann man relativ leicht bestimmen, weil ja 73 = 70 + 3 = 7 ⋅ 10 + 3 ist.

97 mod 10 ≡ 7 mod 10 kann man relativ leicht bestimmen, weil ja 97 = 90 + 7 = 9 ⋅ 10 + 7 ist.

Somit gilt:

(73 ⋅ 97) mod 10 ≡ (3 ⋅ 7) mod 10 ≡ 21 mod 10 ≡ 1 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: 865¹=865

2: 865²=865¹⁺¹=865¹⋅865¹ ≡ 865⋅865=748225 ≡ 499 mod 937

4: 865⁴=865²⁺²=865²⋅865² ≡ 499⋅499=249001 ≡ 696 mod 937

8: 865⁸=865⁴⁺⁴=865⁴⋅865⁴ ≡ 696⋅696=484416 ≡ 924 mod 937

16: 865¹⁶=865⁸⁺⁸=865⁸⋅865⁸ ≡ 924⋅924=853776 ≡ 169 mod 937

32: 865³²=865¹⁶⁺¹⁶=865¹⁶⋅865¹⁶ ≡ 169⋅169=28561 ≡ 451 mod 937

64: 865⁶⁴=865³²⁺³²=865³²⋅865³² ≡ 451⋅451=203401 ≡ 72 mod 937

128: 865¹²⁸=865⁶⁴⁺⁶⁴=865⁶⁴⋅865⁶⁴ ≡ 72⋅72=5184 ≡ 499 mod 937

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

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

153 = 128+16+8+1

225¹⁵³

= 225^128+16+8+1

= 225¹²⁸⋅225¹⁶⋅225⁸⋅225¹

≡ 316 ⋅ 13 ⋅ 32 ⋅ 225 mod 337
≡ 4108 ⋅ 32 ⋅ 225 mod 337 ≡ 64 ⋅ 32 ⋅ 225 mod 337
≡ 2048 ⋅ 225 mod 337 ≡ 26 ⋅ 225 mod 337
≡ 5850 mod 337 ≡ 121 mod 337

Es gilt also: 225¹⁵³ ≡ 121 mod 337

Berechnung des größten gemeinsamen Teilers von 71 und 31

=>71	= 2⋅31 + 9
=>31	= 3⋅9 + 4
=>9	= 2⋅4 + 1
=>4	= 4⋅1 + 0

also gilt: ggt(71,31)=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= 9-2⋅4
4= 31-3⋅9	eingesetzt in die Zeile drüber:	1	= 1⋅9 -2⋅(31 -3⋅ 9) = 1⋅9 -2⋅31 +6⋅ 9) = -2⋅31 +7⋅ 9 (=1)
9= 71-2⋅31	eingesetzt in die Zeile drüber:	1	= -2⋅31 +7⋅(71 -2⋅ 31) = -2⋅31 +7⋅71 -14⋅ 31) = 7⋅71 -16⋅ 31 (=1)

Es gilt also: ggt(71,31)=1 = 7⋅71 -16⋅31

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

1 -7⋅71 = -16⋅31

-16⋅31 = -7⋅71 + 1 |+71⋅31

-16⋅31 + 71⋅31 = -7⋅71 + 71⋅31 + 1

(-16 + 71) ⋅ 31 = (-7 + 31) ⋅ 71 + 1

55⋅31 = 24⋅71 + 1

Es gilt also: 55⋅31 = 24⋅71 +1

Somit 55⋅31 = 1 mod 71

55 ist also das Inverse von 31 mod 71