Um längere Rechnungen zu vermeiden, rechnen wir:

(902 - 28) mod 3 ≡ (902 mod 3 - 28 mod 3) mod 3.

902 mod 3 ≡ 2 mod 3 kann man relativ leicht bestimmen, weil ja 902 = 900+2 = 3 ⋅ 300 +2.

28 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 28 = 30-2 = 3 ⋅ 10 -2 = 3 ⋅ 10 - 3 + 1.

Somit gilt:

(902 - 28) mod 3 ≡ (2 - 1) mod 3 ≡ 1 mod 3.

Um längere Rechnungen zu vermeiden, rechnen wir:

(57 ⋅ 91) mod 5 ≡ (57 mod 5 ⋅ 91 mod 5) mod 5.

57 mod 5 ≡ 2 mod 5 kann man relativ leicht bestimmen, weil ja 57 = 55 + 2 = 11 ⋅ 5 + 2 ist.

91 mod 5 ≡ 1 mod 5 kann man relativ leicht bestimmen, weil ja 91 = 90 + 1 = 18 ⋅ 5 + 1 ist.

Somit gilt:

(57 ⋅ 91) mod 5 ≡ (2 ⋅ 1) mod 5 ≡ 2 mod 5.

Die 32 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: 384¹=384

2: 384²=384¹⁺¹=384¹⋅384¹ ≡ 384⋅384=147456 ≡ 671 mod 947

4: 384⁴=384²⁺²=384²⋅384² ≡ 671⋅671=450241 ≡ 416 mod 947

8: 384⁸=384⁴⁺⁴=384⁴⋅384⁴ ≡ 416⋅416=173056 ≡ 702 mod 947

16: 384¹⁶=384⁸⁺⁸=384⁸⋅384⁸ ≡ 702⋅702=492804 ≡ 364 mod 947

32: 384³²=384¹⁶⁺¹⁶=384¹⁶⋅384¹⁶ ≡ 364⋅364=132496 ≡ 863 mod 947

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

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

239 = 128+64+32+8+4+2+1

536²³⁹

= 536^{128+64+32+8+4+2+1}

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

≡ 97 ⋅ 431 ⋅ 706 ⋅ 431 ⋅ 706 ⋅ 97 ⋅ 536 mod 967
≡ 41807 ⋅ 706 ⋅ 431 ⋅ 706 ⋅ 97 ⋅ 536 mod 967 ≡ 226 ⋅ 706 ⋅ 431 ⋅ 706 ⋅ 97 ⋅ 536 mod 967
≡ 159556 ⋅ 431 ⋅ 706 ⋅ 97 ⋅ 536 mod 967 ≡ 1 ⋅ 431 ⋅ 706 ⋅ 97 ⋅ 536 mod 967
≡ 431 ⋅ 706 ⋅ 97 ⋅ 536 mod 967
≡ 304286 ⋅ 97 ⋅ 536 mod 967 ≡ 648 ⋅ 97 ⋅ 536 mod 967
≡ 62856 ⋅ 536 mod 967 ≡ 1 ⋅ 536 mod 967
≡ 536 mod 967

Es gilt also: 536²³⁹ ≡ 536 mod 967

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

=>71	= 1⋅49 + 22
=>49	= 2⋅22 + 5
=>22	= 4⋅5 + 2
=>5	= 2⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(71,49)=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= 22-4⋅5	eingesetzt in die Zeile drüber:	1	= 1⋅5 -2⋅(22 -4⋅ 5) = 1⋅5 -2⋅22 +8⋅ 5) = -2⋅22 +9⋅ 5 (=1)
5= 49-2⋅22	eingesetzt in die Zeile drüber:	1	= -2⋅22 +9⋅(49 -2⋅ 22) = -2⋅22 +9⋅49 -18⋅ 22) = 9⋅49 -20⋅ 22 (=1)
22= 71-1⋅49	eingesetzt in die Zeile drüber:	1	= 9⋅49 -20⋅(71 -1⋅ 49) = 9⋅49 -20⋅71 +20⋅ 49) = -20⋅71 +29⋅ 49 (=1)

Es gilt also: ggt(71,49)=1 = -20⋅71 +29⋅49

oder wenn man -20⋅71 auf die linke Seite bringt:

1 +20⋅71 = +29⋅49

Es gilt also: 29⋅49 = 20⋅71 +1

Somit 29⋅49 = 1 mod 71

29 ist also das Inverse von 49 mod 71