Um längere Rechnungen zu vermeiden, rechnen wir:

(40006 - 40001) mod 8 ≡ (40006 mod 8 - 40001 mod 8) mod 8.

40006 mod 8 ≡ 6 mod 8 kann man relativ leicht bestimmen, weil ja 40006 = 40000+6 = 8 ⋅ 5000 +6.

40001 mod 8 ≡ 1 mod 8 kann man relativ leicht bestimmen, weil ja 40001 = 40000+1 = 8 ⋅ 5000 +1.

Somit gilt:

(40006 - 40001) mod 8 ≡ (6 - 1) mod 8 ≡ 5 mod 8.

Um längere Rechnungen zu vermeiden, rechnen wir:

(71 ⋅ 37) mod 5 ≡ (71 mod 5 ⋅ 37 mod 5) mod 5.

71 mod 5 ≡ 1 mod 5 kann man relativ leicht bestimmen, weil ja 71 = 70 + 1 = 14 ⋅ 5 + 1 ist.

37 mod 5 ≡ 2 mod 5 kann man relativ leicht bestimmen, weil ja 37 = 35 + 2 = 7 ⋅ 5 + 2 ist.

Somit gilt:

(71 ⋅ 37) mod 5 ≡ (1 ⋅ 2) mod 5 ≡ 2 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: 335¹=335

2: 335²=335¹⁺¹=335¹⋅335¹ ≡ 335⋅335=112225 ≡ 424 mod 449

4: 335⁴=335²⁺²=335²⋅335² ≡ 424⋅424=179776 ≡ 176 mod 449

8: 335⁸=335⁴⁺⁴=335⁴⋅335⁴ ≡ 176⋅176=30976 ≡ 444 mod 449

16: 335¹⁶=335⁸⁺⁸=335⁸⋅335⁸ ≡ 444⋅444=197136 ≡ 25 mod 449

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

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

211 = 128+64+16+2+1

688²¹¹

= 688^{128+64+16+2+1}

= 688¹²⁸⋅688⁶⁴⋅688¹⁶⋅688²⋅688¹

≡ 360 ⋅ 408 ⋅ 408 ⋅ 409 ⋅ 688 mod 769
≡ 146880 ⋅ 408 ⋅ 409 ⋅ 688 mod 769 ≡ 1 ⋅ 408 ⋅ 409 ⋅ 688 mod 769
≡ 408 ⋅ 409 ⋅ 688 mod 769
≡ 166872 ⋅ 688 mod 769 ≡ 768 ⋅ 688 mod 769
≡ 528384 mod 769 ≡ 81 mod 769

Es gilt also: 688²¹¹ ≡ 81 mod 769

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