Um längere Rechnungen zu vermeiden, rechnen wir:

(303 - 149) mod 3 ≡ (303 mod 3 - 149 mod 3) mod 3.

303 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 303 = 300+3 = 3 ⋅ 100 +3.

149 mod 3 ≡ 2 mod 3 kann man relativ leicht bestimmen, weil ja 149 = 150-1 = 3 ⋅ 50 -1 = 3 ⋅ 50 - 3 + 2.

Somit gilt:

(303 - 149) mod 3 ≡ (0 - 2) mod 3 ≡ -2 mod 3 ≡ 1 mod 3.

Um längere Rechnungen zu vermeiden, rechnen wir:

(39 ⋅ 21) mod 9 ≡ (39 mod 9 ⋅ 21 mod 9) mod 9.

39 mod 9 ≡ 3 mod 9 kann man relativ leicht bestimmen, weil ja 39 = 36 + 3 = 4 ⋅ 9 + 3 ist.

21 mod 9 ≡ 3 mod 9 kann man relativ leicht bestimmen, weil ja 21 = 18 + 3 = 2 ⋅ 9 + 3 ist.

Somit gilt:

(39 ⋅ 21) mod 9 ≡ (3 ⋅ 3) mod 9 ≡ 9 mod 9 ≡ 0 mod 9.

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

2: 278²=278¹⁺¹=278¹⋅278¹ ≡ 278⋅278=77284 ≡ 194 mod 593

4: 278⁴=278²⁺²=278²⋅278² ≡ 194⋅194=37636 ≡ 277 mod 593

8: 278⁸=278⁴⁺⁴=278⁴⋅278⁴ ≡ 277⋅277=76729 ≡ 232 mod 593

16: 278¹⁶=278⁸⁺⁸=278⁸⋅278⁸ ≡ 232⋅232=53824 ≡ 454 mod 593

32: 278³²=278¹⁶⁺¹⁶=278¹⁶⋅278¹⁶ ≡ 454⋅454=206116 ≡ 345 mod 593

64: 278⁶⁴=278³²⁺³²=278³²⋅278³² ≡ 345⋅345=119025 ≡ 425 mod 593

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

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

217 = 128+64+16+8+1

675²¹⁷

= 675^{128+64+16+8+1}

= 675¹²⁸⋅675⁶⁴⋅675¹⁶⋅675⁸⋅675¹

≡ 564 ⋅ 228 ⋅ 43 ⋅ 827 ⋅ 675 mod 857
≡ 128592 ⋅ 43 ⋅ 827 ⋅ 675 mod 857 ≡ 42 ⋅ 43 ⋅ 827 ⋅ 675 mod 857
≡ 1806 ⋅ 827 ⋅ 675 mod 857 ≡ 92 ⋅ 827 ⋅ 675 mod 857
≡ 76084 ⋅ 675 mod 857 ≡ 668 ⋅ 675 mod 857
≡ 450900 mod 857 ≡ 118 mod 857

Es gilt also: 675²¹⁷ ≡ 118 mod 857

Berechnung des größten gemeinsamen Teilers von 89 und 70

=>89	= 1⋅70 + 19
=>70	= 3⋅19 + 13
=>19	= 1⋅13 + 6
=>13	= 2⋅6 + 1
=>6	= 6⋅1 + 0

also gilt: ggt(89,70)=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= 13-2⋅6
6= 19-1⋅13	eingesetzt in die Zeile drüber:	1	= 1⋅13 -2⋅(19 -1⋅ 13) = 1⋅13 -2⋅19 +2⋅ 13) = -2⋅19 +3⋅ 13 (=1)
13= 70-3⋅19	eingesetzt in die Zeile drüber:	1	= -2⋅19 +3⋅(70 -3⋅ 19) = -2⋅19 +3⋅70 -9⋅ 19) = 3⋅70 -11⋅ 19 (=1)
19= 89-1⋅70	eingesetzt in die Zeile drüber:	1	= 3⋅70 -11⋅(89 -1⋅ 70) = 3⋅70 -11⋅89 +11⋅ 70) = -11⋅89 +14⋅ 70 (=1)

Es gilt also: ggt(89,70)=1 = -11⋅89 +14⋅70

oder wenn man -11⋅89 auf die linke Seite bringt:

1 +11⋅89 = +14⋅70

Es gilt also: 14⋅70 = 11⋅89 +1

Somit 14⋅70 = 1 mod 89

14 ist also das Inverse von 70 mod 89