Um längere Rechnungen zu vermeiden, rechnen wir:

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

14998 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 14998 = 15000-2 = 3 ⋅ 5000 -2 = 3 ⋅ 5000 - 3 + 1.

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

Somit gilt:

(14998 - 3000) mod 3 ≡ (1 - 0) mod 3 ≡ 1 mod 3.

Um längere Rechnungen zu vermeiden, rechnen wir:

(28 ⋅ 80) mod 3 ≡ (28 mod 3 ⋅ 80 mod 3) mod 3.

28 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 28 = 27 + 1 = 9 ⋅ 3 + 1 ist.

80 mod 3 ≡ 2 mod 3 kann man relativ leicht bestimmen, weil ja 80 = 78 + 2 = 26 ⋅ 3 + 2 ist.

Somit gilt:

(28 ⋅ 80) mod 3 ≡ (1 ⋅ 2) mod 3 ≡ 2 mod 3.

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

2: 432²=432¹⁺¹=432¹⋅432¹ ≡ 432⋅432=186624 ≡ 216 mod 863

4: 432⁴=432²⁺²=432²⋅432² ≡ 216⋅216=46656 ≡ 54 mod 863

8: 432⁸=432⁴⁺⁴=432⁴⋅432⁴ ≡ 54⋅54=2916 ≡ 327 mod 863

16: 432¹⁶=432⁸⁺⁸=432⁸⋅432⁸ ≡ 327⋅327=106929 ≡ 780 mod 863

32: 432³²=432¹⁶⁺¹⁶=432¹⁶⋅432¹⁶ ≡ 780⋅780=608400 ≡ 848 mod 863

64: 432⁶⁴=432³²⁺³²=432³²⋅432³² ≡ 848⋅848=719104 ≡ 225 mod 863

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

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

221 = 128+64+16+8+4+1

632²²¹

= 632^{128+64+16+8+4+1}

= 632¹²⁸⋅632⁶⁴⋅632¹⁶⋅632⁸⋅632⁴⋅632¹

≡ 697 ⋅ 431 ⋅ 472 ⋅ 480 ⋅ 286 ⋅ 632 mod 701
≡ 300407 ⋅ 472 ⋅ 480 ⋅ 286 ⋅ 632 mod 701 ≡ 379 ⋅ 472 ⋅ 480 ⋅ 286 ⋅ 632 mod 701
≡ 178888 ⋅ 480 ⋅ 286 ⋅ 632 mod 701 ≡ 133 ⋅ 480 ⋅ 286 ⋅ 632 mod 701
≡ 63840 ⋅ 286 ⋅ 632 mod 701 ≡ 49 ⋅ 286 ⋅ 632 mod 701
≡ 14014 ⋅ 632 mod 701 ≡ 695 ⋅ 632 mod 701
≡ 439240 mod 701 ≡ 414 mod 701

Es gilt also: 632²²¹ ≡ 414 mod 701

Berechnung des größten gemeinsamen Teilers von 83 und 54

=>83	= 1⋅54 + 29
=>54	= 1⋅29 + 25
=>29	= 1⋅25 + 4
=>25	= 6⋅4 + 1
=>4	= 4⋅1 + 0

also gilt: ggt(83,54)=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= 25-6⋅4
4= 29-1⋅25	eingesetzt in die Zeile drüber:	1	= 1⋅25 -6⋅(29 -1⋅ 25) = 1⋅25 -6⋅29 +6⋅ 25) = -6⋅29 +7⋅ 25 (=1)
25= 54-1⋅29	eingesetzt in die Zeile drüber:	1	= -6⋅29 +7⋅(54 -1⋅ 29) = -6⋅29 +7⋅54 -7⋅ 29) = 7⋅54 -13⋅ 29 (=1)
29= 83-1⋅54	eingesetzt in die Zeile drüber:	1	= 7⋅54 -13⋅(83 -1⋅ 54) = 7⋅54 -13⋅83 +13⋅ 54) = -13⋅83 +20⋅ 54 (=1)

Es gilt also: ggt(83,54)=1 = -13⋅83 +20⋅54

oder wenn man -13⋅83 auf die linke Seite bringt:

1 +13⋅83 = +20⋅54

Es gilt also: 20⋅54 = 13⋅83 +1

Somit 20⋅54 = 1 mod 83

20 ist also das Inverse von 54 mod 83