Um längere Rechnungen zu vermeiden, rechnen wir:

(150 - 3000) mod 3 ≡ (150 mod 3 - 3000 mod 3) mod 3.

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

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

Somit gilt:

(150 - 3000) mod 3 ≡ (0 - 0) mod 3 ≡ 0 mod 3.

Um längere Rechnungen zu vermeiden, rechnen wir:

(58 ⋅ 84) mod 7 ≡ (58 mod 7 ⋅ 84 mod 7) mod 7.

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

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

Somit gilt:

(58 ⋅ 84) mod 7 ≡ (2 ⋅ 0) mod 7 ≡ 0 mod 7.

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

2: 440²=440¹⁺¹=440¹⋅440¹ ≡ 440⋅440=193600 ≡ 477 mod 587

4: 440⁴=440²⁺²=440²⋅440² ≡ 477⋅477=227529 ≡ 360 mod 587

8: 440⁸=440⁴⁺⁴=440⁴⋅440⁴ ≡ 360⋅360=129600 ≡ 460 mod 587

16: 440¹⁶=440⁸⁺⁸=440⁸⋅440⁸ ≡ 460⋅460=211600 ≡ 280 mod 587

32: 440³²=440¹⁶⁺¹⁶=440¹⁶⋅440¹⁶ ≡ 280⋅280=78400 ≡ 329 mod 587

64: 440⁶⁴=440³²⁺³²=440³²⋅440³² ≡ 329⋅329=108241 ≡ 233 mod 587

128: 440¹²⁸=440⁶⁴⁺⁶⁴=440⁶⁴⋅440⁶⁴ ≡ 233⋅233=54289 ≡ 285 mod 587

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

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

241 = 128+64+32+16+1

145²⁴¹

= 145^{128+64+32+16+1}

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

≡ 12 ⋅ 417 ⋅ 326 ⋅ 184 ⋅ 145 mod 479
≡ 5004 ⋅ 326 ⋅ 184 ⋅ 145 mod 479 ≡ 214 ⋅ 326 ⋅ 184 ⋅ 145 mod 479
≡ 69764 ⋅ 184 ⋅ 145 mod 479 ≡ 309 ⋅ 184 ⋅ 145 mod 479
≡ 56856 ⋅ 145 mod 479 ≡ 334 ⋅ 145 mod 479
≡ 48430 mod 479 ≡ 51 mod 479

Es gilt also: 145²⁴¹ ≡ 51 mod 479

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

=>97	= 2⋅33 + 31
=>33	= 1⋅31 + 2
=>31	= 15⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(97,33)=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= 31-15⋅2
2= 33-1⋅31	eingesetzt in die Zeile drüber:	1	= 1⋅31 -15⋅(33 -1⋅ 31) = 1⋅31 -15⋅33 +15⋅ 31) = -15⋅33 +16⋅ 31 (=1)
31= 97-2⋅33	eingesetzt in die Zeile drüber:	1	= -15⋅33 +16⋅(97 -2⋅ 33) = -15⋅33 +16⋅97 -32⋅ 33) = 16⋅97 -47⋅ 33 (=1)

Es gilt also: ggt(97,33)=1 = 16⋅97 -47⋅33

oder wenn man 16⋅97 auf die linke Seite bringt:

1 -16⋅97 = -47⋅33

-47⋅33 = -16⋅97 + 1 |+97⋅33

-47⋅33 + 97⋅33 = -16⋅97 + 97⋅33 + 1

(-47 + 97) ⋅ 33 = (-16 + 33) ⋅ 97 + 1

50⋅33 = 17⋅97 + 1

Es gilt also: 50⋅33 = 17⋅97 +1

Somit 50⋅33 = 1 mod 97

50 ist also das Inverse von 33 mod 97