Um längere Rechnungen zu vermeiden, rechnen wir:

(1500 + 14999) mod 3 ≡ (1500 mod 3 + 14999 mod 3) mod 3.

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

14999 mod 3 ≡ 2 mod 3 kann man relativ leicht bestimmen, weil ja 14999 = 15000-1 = 3 ⋅ 5000 -1 = 3 ⋅ 5000 - 3 + 2.

Somit gilt:

(1500 + 14999) mod 3 ≡ (0 + 2) mod 3 ≡ 2 mod 3.

Um längere Rechnungen zu vermeiden, rechnen wir:

(58 ⋅ 21) mod 4 ≡ (58 mod 4 ⋅ 21 mod 4) mod 4.

58 mod 4 ≡ 2 mod 4 kann man relativ leicht bestimmen, weil ja 58 = 56 + 2 = 14 ⋅ 4 + 2 ist.

21 mod 4 ≡ 1 mod 4 kann man relativ leicht bestimmen, weil ja 21 = 20 + 1 = 5 ⋅ 4 + 1 ist.

Somit gilt:

(58 ⋅ 21) mod 4 ≡ (2 ⋅ 1) mod 4 ≡ 2 mod 4.

Die 64 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: 316¹=316

2: 316²=316¹⁺¹=316¹⋅316¹ ≡ 316⋅316=99856 ≡ 54 mod 359

4: 316⁴=316²⁺²=316²⋅316² ≡ 54⋅54=2916 ≡ 44 mod 359

8: 316⁸=316⁴⁺⁴=316⁴⋅316⁴ ≡ 44⋅44=1936 ≡ 141 mod 359

16: 316¹⁶=316⁸⁺⁸=316⁸⋅316⁸ ≡ 141⋅141=19881 ≡ 136 mod 359

32: 316³²=316¹⁶⁺¹⁶=316¹⁶⋅316¹⁶ ≡ 136⋅136=18496 ≡ 187 mod 359

64: 316⁶⁴=316³²⁺³²=316³²⋅316³² ≡ 187⋅187=34969 ≡ 146 mod 359

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

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

227 = 128+64+32+2+1

331²²⁷

= 331^{128+64+32+2+1}

= 331¹²⁸⋅331⁶⁴⋅331³²⋅331²⋅331¹

≡ 353 ⋅ 425 ⋅ 345 ⋅ 449 ⋅ 331 mod 593
≡ 150025 ⋅ 345 ⋅ 449 ⋅ 331 mod 593 ≡ 589 ⋅ 345 ⋅ 449 ⋅ 331 mod 593
≡ 203205 ⋅ 449 ⋅ 331 mod 593 ≡ 399 ⋅ 449 ⋅ 331 mod 593
≡ 179151 ⋅ 331 mod 593 ≡ 65 ⋅ 331 mod 593
≡ 21515 mod 593 ≡ 167 mod 593

Es gilt also: 331²²⁷ ≡ 167 mod 593

Berechnung des größten gemeinsamen Teilers von 97 und 88

=>97	= 1⋅88 + 9
=>88	= 9⋅9 + 7
=>9	= 1⋅7 + 2
=>7	= 3⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(97,88)=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= 7-3⋅2
2= 9-1⋅7	eingesetzt in die Zeile drüber:	1	= 1⋅7 -3⋅(9 -1⋅ 7) = 1⋅7 -3⋅9 +3⋅ 7) = -3⋅9 +4⋅ 7 (=1)
7= 88-9⋅9	eingesetzt in die Zeile drüber:	1	= -3⋅9 +4⋅(88 -9⋅ 9) = -3⋅9 +4⋅88 -36⋅ 9) = 4⋅88 -39⋅ 9 (=1)
9= 97-1⋅88	eingesetzt in die Zeile drüber:	1	= 4⋅88 -39⋅(97 -1⋅ 88) = 4⋅88 -39⋅97 +39⋅ 88) = -39⋅97 +43⋅ 88 (=1)

Es gilt also: ggt(97,88)=1 = -39⋅97 +43⋅88

oder wenn man -39⋅97 auf die linke Seite bringt:

1 +39⋅97 = +43⋅88

Es gilt also: 43⋅88 = 39⋅97 +1

Somit 43⋅88 = 1 mod 97

43 ist also das Inverse von 88 mod 97