Um längere Rechnungen zu vermeiden, rechnen wir:

(284 - 696) mod 7 ≡ (284 mod 7 - 696 mod 7) mod 7.

284 mod 7 ≡ 4 mod 7 kann man relativ leicht bestimmen, weil ja 284 = 280+4 = 7 ⋅ 40 +4.

696 mod 7 ≡ 3 mod 7 kann man relativ leicht bestimmen, weil ja 696 = 700-4 = 7 ⋅ 100 -4 = 7 ⋅ 100 - 7 + 3.

Somit gilt:

(284 - 696) mod 7 ≡ (4 - 3) mod 7 ≡ 1 mod 7.

Um längere Rechnungen zu vermeiden, rechnen wir:

(46 ⋅ 65) mod 3 ≡ (46 mod 3 ⋅ 65 mod 3) mod 3.

46 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 46 = 45 + 1 = 15 ⋅ 3 + 1 ist.

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

Somit gilt:

(46 ⋅ 65) mod 3 ≡ (1 ⋅ 2) mod 3 ≡ 2 mod 3.

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

2: 484²=484¹⁺¹=484¹⋅484¹ ≡ 484⋅484=234256 ≡ 608 mod 859

4: 484⁴=484²⁺²=484²⋅484² ≡ 608⋅608=369664 ≡ 294 mod 859

8: 484⁸=484⁴⁺⁴=484⁴⋅484⁴ ≡ 294⋅294=86436 ≡ 536 mod 859

16: 484¹⁶=484⁸⁺⁸=484⁸⋅484⁸ ≡ 536⋅536=287296 ≡ 390 mod 859

32: 484³²=484¹⁶⁺¹⁶=484¹⁶⋅484¹⁶ ≡ 390⋅390=152100 ≡ 57 mod 859

64: 484⁶⁴=484³²⁺³²=484³²⋅484³² ≡ 57⋅57=3249 ≡ 672 mod 859

128: 484¹²⁸=484⁶⁴⁺⁶⁴=484⁶⁴⋅484⁶⁴ ≡ 672⋅672=451584 ≡ 609 mod 859

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

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

225 = 128+64+32+1

134²²⁵

= 134^128+64+32+1

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

≡ 205 ⋅ 81 ⋅ 9 ⋅ 134 mod 227
≡ 16605 ⋅ 9 ⋅ 134 mod 227 ≡ 34 ⋅ 9 ⋅ 134 mod 227
≡ 306 ⋅ 134 mod 227 ≡ 79 ⋅ 134 mod 227
≡ 10586 mod 227 ≡ 144 mod 227

Es gilt also: 134²²⁵ ≡ 144 mod 227

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

=>89	= 1⋅52 + 37
=>52	= 1⋅37 + 15
=>37	= 2⋅15 + 7
=>15	= 2⋅7 + 1
=>7	= 7⋅1 + 0

also gilt: ggt(89,52)=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= 15-2⋅7
7= 37-2⋅15	eingesetzt in die Zeile drüber:	1	= 1⋅15 -2⋅(37 -2⋅ 15) = 1⋅15 -2⋅37 +4⋅ 15) = -2⋅37 +5⋅ 15 (=1)
15= 52-1⋅37	eingesetzt in die Zeile drüber:	1	= -2⋅37 +5⋅(52 -1⋅ 37) = -2⋅37 +5⋅52 -5⋅ 37) = 5⋅52 -7⋅ 37 (=1)
37= 89-1⋅52	eingesetzt in die Zeile drüber:	1	= 5⋅52 -7⋅(89 -1⋅ 52) = 5⋅52 -7⋅89 +7⋅ 52) = -7⋅89 +12⋅ 52 (=1)

Es gilt also: ggt(89,52)=1 = -7⋅89 +12⋅52

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

1 +7⋅89 = +12⋅52

Es gilt also: 12⋅52 = 7⋅89 +1

Somit 12⋅52 = 1 mod 89

12 ist also das Inverse von 52 mod 89