Um längere Rechnungen zu vermeiden, rechnen wir:

(62 - 9001) mod 3 ≡ (62 mod 3 - 9001 mod 3) mod 3.

62 mod 3 ≡ 2 mod 3 kann man relativ leicht bestimmen, weil ja 62 = 60+2 = 3 ⋅ 20 +2.

9001 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 9001 = 9000+1 = 3 ⋅ 3000 +1.

Somit gilt:

(62 - 9001) mod 3 ≡ (2 - 1) mod 3 ≡ 1 mod 3.

Um längere Rechnungen zu vermeiden, rechnen wir:

(69 ⋅ 18) mod 6 ≡ (69 mod 6 ⋅ 18 mod 6) mod 6.

69 mod 6 ≡ 3 mod 6 kann man relativ leicht bestimmen, weil ja 69 = 66 + 3 = 11 ⋅ 6 + 3 ist.

18 mod 6 ≡ 0 mod 6 kann man relativ leicht bestimmen, weil ja 18 = 18 + 0 = 3 ⋅ 6 + 0 ist.

Somit gilt:

(69 ⋅ 18) mod 6 ≡ (3 ⋅ 0) mod 6 ≡ 0 mod 6.

Die 16 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: 976¹=976

2: 976²=976¹⁺¹=976¹⋅976¹ ≡ 976⋅976=952576 ≡ 225 mod 991

4: 976⁴=976²⁺²=976²⋅976² ≡ 225⋅225=50625 ≡ 84 mod 991

8: 976⁸=976⁴⁺⁴=976⁴⋅976⁴ ≡ 84⋅84=7056 ≡ 119 mod 991

16: 976¹⁶=976⁸⁺⁸=976⁸⋅976⁸ ≡ 119⋅119=14161 ≡ 287 mod 991

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

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

245 = 128+64+32+16+4+1

116²⁴⁵

= 116^{128+64+32+16+4+1}

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

≡ 29 ⋅ 38 ⋅ 86 ⋅ 54 ⋅ 253 ⋅ 116 mod 283
≡ 1102 ⋅ 86 ⋅ 54 ⋅ 253 ⋅ 116 mod 283 ≡ 253 ⋅ 86 ⋅ 54 ⋅ 253 ⋅ 116 mod 283
≡ 21758 ⋅ 54 ⋅ 253 ⋅ 116 mod 283 ≡ 250 ⋅ 54 ⋅ 253 ⋅ 116 mod 283
≡ 13500 ⋅ 253 ⋅ 116 mod 283 ≡ 199 ⋅ 253 ⋅ 116 mod 283
≡ 50347 ⋅ 116 mod 283 ≡ 256 ⋅ 116 mod 283
≡ 29696 mod 283 ≡ 264 mod 283

Es gilt also: 116²⁴⁵ ≡ 264 mod 283

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

=>97	= 2⋅45 + 7
=>45	= 6⋅7 + 3
=>7	= 2⋅3 + 1
=>3	= 3⋅1 + 0

also gilt: ggt(97,45)=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= 7-2⋅3
3= 45-6⋅7	eingesetzt in die Zeile drüber:	1	= 1⋅7 -2⋅(45 -6⋅ 7) = 1⋅7 -2⋅45 +12⋅ 7) = -2⋅45 +13⋅ 7 (=1)
7= 97-2⋅45	eingesetzt in die Zeile drüber:	1	= -2⋅45 +13⋅(97 -2⋅ 45) = -2⋅45 +13⋅97 -26⋅ 45) = 13⋅97 -28⋅ 45 (=1)

Es gilt also: ggt(97,45)=1 = 13⋅97 -28⋅45

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

1 -13⋅97 = -28⋅45

-28⋅45 = -13⋅97 + 1 |+97⋅45

-28⋅45 + 97⋅45 = -13⋅97 + 97⋅45 + 1

(-28 + 97) ⋅ 45 = (-13 + 45) ⋅ 97 + 1

69⋅45 = 32⋅97 + 1

Es gilt also: 69⋅45 = 32⋅97 +1

Somit 69⋅45 = 1 mod 97

69 ist also das Inverse von 45 mod 97