Um längere Rechnungen zu vermeiden, rechnen wir:

(154 - 15993) mod 8 ≡ (154 mod 8 - 15993 mod 8) mod 8.

154 mod 8 ≡ 2 mod 8 kann man relativ leicht bestimmen, weil ja 154 = 160-6 = 8 ⋅ 20 -6 = 8 ⋅ 20 - 8 + 2.

15993 mod 8 ≡ 1 mod 8 kann man relativ leicht bestimmen, weil ja 15993 = 15000+993 = 8 ⋅ 1875 +993.

Somit gilt:

(154 - 15993) mod 8 ≡ (2 - 1) mod 8 ≡ 1 mod 8.

Um längere Rechnungen zu vermeiden, rechnen wir:

(68 ⋅ 72) mod 8 ≡ (68 mod 8 ⋅ 72 mod 8) mod 8.

68 mod 8 ≡ 4 mod 8 kann man relativ leicht bestimmen, weil ja 68 = 64 + 4 = 8 ⋅ 8 + 4 ist.

72 mod 8 ≡ 0 mod 8 kann man relativ leicht bestimmen, weil ja 72 = 72 + 0 = 9 ⋅ 8 + 0 ist.

Somit gilt:

(68 ⋅ 72) mod 8 ≡ (4 ⋅ 0) mod 8 ≡ 0 mod 8.

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

2: 416²=416¹⁺¹=416¹⋅416¹ ≡ 416⋅416=173056 ≡ 181 mod 461

4: 416⁴=416²⁺²=416²⋅416² ≡ 181⋅181=32761 ≡ 30 mod 461

8: 416⁸=416⁴⁺⁴=416⁴⋅416⁴ ≡ 30⋅30=900 ≡ 439 mod 461

16: 416¹⁶=416⁸⁺⁸=416⁸⋅416⁸ ≡ 439⋅439=192721 ≡ 23 mod 461

32: 416³²=416¹⁶⁺¹⁶=416¹⁶⋅416¹⁶ ≡ 23⋅23=529 ≡ 68 mod 461

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

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

236 = 128+64+32+8+4

576²³⁶

= 576^{128+64+32+8+4}

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

≡ 824 ⋅ 576 ⋅ 985 ⋅ 507 ⋅ 928 mod 1009
≡ 474624 ⋅ 985 ⋅ 507 ⋅ 928 mod 1009 ≡ 394 ⋅ 985 ⋅ 507 ⋅ 928 mod 1009
≡ 388090 ⋅ 507 ⋅ 928 mod 1009 ≡ 634 ⋅ 507 ⋅ 928 mod 1009
≡ 321438 ⋅ 928 mod 1009 ≡ 576 ⋅ 928 mod 1009
≡ 534528 mod 1009 ≡ 767 mod 1009

Es gilt also: 576²³⁶ ≡ 767 mod 1009

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

=>83	= 2⋅39 + 5
=>39	= 7⋅5 + 4
=>5	= 1⋅4 + 1
=>4	= 4⋅1 + 0

also gilt: ggt(83,39)=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-1⋅4
4= 39-7⋅5	eingesetzt in die Zeile drüber:	1	= 1⋅5 -1⋅(39 -7⋅ 5) = 1⋅5 -1⋅39 +7⋅ 5) = -1⋅39 +8⋅ 5 (=1)
5= 83-2⋅39	eingesetzt in die Zeile drüber:	1	= -1⋅39 +8⋅(83 -2⋅ 39) = -1⋅39 +8⋅83 -16⋅ 39) = 8⋅83 -17⋅ 39 (=1)

Es gilt also: ggt(83,39)=1 = 8⋅83 -17⋅39

oder wenn man 8⋅83 auf die linke Seite bringt:

1 -8⋅83 = -17⋅39

-17⋅39 = -8⋅83 + 1 |+83⋅39

-17⋅39 + 83⋅39 = -8⋅83 + 83⋅39 + 1

(-17 + 83) ⋅ 39 = (-8 + 39) ⋅ 83 + 1

66⋅39 = 31⋅83 + 1

Es gilt also: 66⋅39 = 31⋅83 +1

Somit 66⋅39 = 1 mod 83

66 ist also das Inverse von 39 mod 83