Um längere Rechnungen zu vermeiden, rechnen wir:

(796 - 1600) mod 4 ≡ (796 mod 4 - 1600 mod 4) mod 4.

796 mod 4 ≡ 0 mod 4 kann man relativ leicht bestimmen, weil ja 796 = 700+96 = 4 ⋅ 175 +96.

1600 mod 4 ≡ 0 mod 4 kann man relativ leicht bestimmen, weil ja 1600 = 1600+0 = 4 ⋅ 400 +0.

Somit gilt:

(796 - 1600) mod 4 ≡ (0 - 0) mod 4 ≡ 0 mod 4.

Um längere Rechnungen zu vermeiden, rechnen wir:

(35 ⋅ 70) mod 5 ≡ (35 mod 5 ⋅ 70 mod 5) mod 5.

35 mod 5 ≡ 0 mod 5 kann man relativ leicht bestimmen, weil ja 35 = 35 + 0 = 7 ⋅ 5 + 0 ist.

70 mod 5 ≡ 0 mod 5 kann man relativ leicht bestimmen, weil ja 70 = 70 + 0 = 14 ⋅ 5 + 0 ist.

Somit gilt:

(35 ⋅ 70) mod 5 ≡ (0 ⋅ 0) mod 5 ≡ 0 mod 5.

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

2: 900²=900¹⁺¹=900¹⋅900¹ ≡ 900⋅900=810000 ≡ 121 mod 911

4: 900⁴=900²⁺²=900²⋅900² ≡ 121⋅121=14641 ≡ 65 mod 911

8: 900⁸=900⁴⁺⁴=900⁴⋅900⁴ ≡ 65⋅65=4225 ≡ 581 mod 911

16: 900¹⁶=900⁸⁺⁸=900⁸⋅900⁸ ≡ 581⋅581=337561 ≡ 491 mod 911

32: 900³²=900¹⁶⁺¹⁶=900¹⁶⋅900¹⁶ ≡ 491⋅491=241081 ≡ 577 mod 911

64: 900⁶⁴=900³²⁺³²=900³²⋅900³² ≡ 577⋅577=332929 ≡ 414 mod 911

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

301²²⁵

= 301^128+64+32+1

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

≡ 571 ⋅ 296 ⋅ 451 ⋅ 301 mod 829
≡ 169016 ⋅ 451 ⋅ 301 mod 829 ≡ 729 ⋅ 451 ⋅ 301 mod 829
≡ 328779 ⋅ 301 mod 829 ≡ 495 ⋅ 301 mod 829
≡ 148995 mod 829 ≡ 604 mod 829

Es gilt also: 301²²⁵ ≡ 604 mod 829

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

=>89	= 1⋅47 + 42
=>47	= 1⋅42 + 5
=>42	= 8⋅5 + 2
=>5	= 2⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(89,47)=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= 5-2⋅2
2= 42-8⋅5	eingesetzt in die Zeile drüber:	1	= 1⋅5 -2⋅(42 -8⋅ 5) = 1⋅5 -2⋅42 +16⋅ 5) = -2⋅42 +17⋅ 5 (=1)
5= 47-1⋅42	eingesetzt in die Zeile drüber:	1	= -2⋅42 +17⋅(47 -1⋅ 42) = -2⋅42 +17⋅47 -17⋅ 42) = 17⋅47 -19⋅ 42 (=1)
42= 89-1⋅47	eingesetzt in die Zeile drüber:	1	= 17⋅47 -19⋅(89 -1⋅ 47) = 17⋅47 -19⋅89 +19⋅ 47) = -19⋅89 +36⋅ 47 (=1)

Es gilt also: ggt(89,47)=1 = -19⋅89 +36⋅47

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

1 +19⋅89 = +36⋅47

Es gilt also: 36⋅47 = 19⋅89 +1

Somit 36⋅47 = 1 mod 89

36 ist also das Inverse von 47 mod 89