Um längere Rechnungen zu vermeiden, rechnen wir:

(2406 + 3200) mod 8 ≡ (2406 mod 8 + 3200 mod 8) mod 8.

2406 mod 8 ≡ 6 mod 8 kann man relativ leicht bestimmen, weil ja 2406 = 2400+6 = 8 ⋅ 300 +6.

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

Somit gilt:

(2406 + 3200) mod 8 ≡ (6 + 0) mod 8 ≡ 6 mod 8.

Um längere Rechnungen zu vermeiden, rechnen wir:

(94 ⋅ 84) mod 5 ≡ (94 mod 5 ⋅ 84 mod 5) mod 5.

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

84 mod 5 ≡ 4 mod 5 kann man relativ leicht bestimmen, weil ja 84 = 80 + 4 = 16 ⋅ 5 + 4 ist.

Somit gilt:

(94 ⋅ 84) mod 5 ≡ (4 ⋅ 4) mod 5 ≡ 16 mod 5 ≡ 1 mod 5.

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

2: 277²=277¹⁺¹=277¹⋅277¹ ≡ 277⋅277=76729 ≡ 278 mod 859

4: 277⁴=277²⁺²=277²⋅277² ≡ 278⋅278=77284 ≡ 833 mod 859

8: 277⁸=277⁴⁺⁴=277⁴⋅277⁴ ≡ 833⋅833=693889 ≡ 676 mod 859

16: 277¹⁶=277⁸⁺⁸=277⁸⋅277⁸ ≡ 676⋅676=456976 ≡ 847 mod 859

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

147²⁴¹

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

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

≡ 25 ⋅ 444 ⋅ 273 ⋅ 121 ⋅ 147 mod 449
≡ 11100 ⋅ 273 ⋅ 121 ⋅ 147 mod 449 ≡ 324 ⋅ 273 ⋅ 121 ⋅ 147 mod 449
≡ 88452 ⋅ 121 ⋅ 147 mod 449 ≡ 448 ⋅ 121 ⋅ 147 mod 449
≡ 54208 ⋅ 147 mod 449 ≡ 328 ⋅ 147 mod 449
≡ 48216 mod 449 ≡ 173 mod 449

Es gilt also: 147²⁴¹ ≡ 173 mod 449

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

=>83	= 1⋅68 + 15
=>68	= 4⋅15 + 8
=>15	= 1⋅8 + 7
=>8	= 1⋅7 + 1
=>7	= 7⋅1 + 0

also gilt: ggt(83,68)=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= 8-1⋅7
7= 15-1⋅8	eingesetzt in die Zeile drüber:	1	= 1⋅8 -1⋅(15 -1⋅ 8) = 1⋅8 -1⋅15 +1⋅ 8) = -1⋅15 +2⋅ 8 (=1)
8= 68-4⋅15	eingesetzt in die Zeile drüber:	1	= -1⋅15 +2⋅(68 -4⋅ 15) = -1⋅15 +2⋅68 -8⋅ 15) = 2⋅68 -9⋅ 15 (=1)
15= 83-1⋅68	eingesetzt in die Zeile drüber:	1	= 2⋅68 -9⋅(83 -1⋅ 68) = 2⋅68 -9⋅83 +9⋅ 68) = -9⋅83 +11⋅ 68 (=1)

Es gilt also: ggt(83,68)=1 = -9⋅83 +11⋅68

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

1 +9⋅83 = +11⋅68

Es gilt also: 11⋅68 = 9⋅83 +1

Somit 11⋅68 = 1 mod 83

11 ist also das Inverse von 68 mod 83