Um längere Rechnungen zu vermeiden, rechnen wir:

(2002 + 7996) mod 4 ≡ (2002 mod 4 + 7996 mod 4) mod 4.

2002 mod 4 ≡ 2 mod 4 kann man relativ leicht bestimmen, weil ja 2002 = 2000+2 = 4 ⋅ 500 +2.

7996 mod 4 ≡ 0 mod 4 kann man relativ leicht bestimmen, weil ja 7996 = 7000+996 = 4 ⋅ 1750 +996.

Somit gilt:

(2002 + 7996) mod 4 ≡ (2 + 0) mod 4 ≡ 2 mod 4.

Um längere Rechnungen zu vermeiden, rechnen wir:

(20 ⋅ 68) mod 5 ≡ (20 mod 5 ⋅ 68 mod 5) mod 5.

20 mod 5 ≡ 0 mod 5 kann man relativ leicht bestimmen, weil ja 20 = 20 + 0 = 4 ⋅ 5 + 0 ist.

68 mod 5 ≡ 3 mod 5 kann man relativ leicht bestimmen, weil ja 68 = 65 + 3 = 13 ⋅ 5 + 3 ist.

Somit gilt:

(20 ⋅ 68) mod 5 ≡ (0 ⋅ 3) mod 5 ≡ 0 mod 5.

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

2: 309²=309¹⁺¹=309¹⋅309¹ ≡ 309⋅309=95481 ≡ 99 mod 757

4: 309⁴=309²⁺²=309²⋅309² ≡ 99⋅99=9801 ≡ 717 mod 757

8: 309⁸=309⁴⁺⁴=309⁴⋅309⁴ ≡ 717⋅717=514089 ≡ 86 mod 757

16: 309¹⁶=309⁸⁺⁸=309⁸⋅309⁸ ≡ 86⋅86=7396 ≡ 583 mod 757

32: 309³²=309¹⁶⁺¹⁶=309¹⁶⋅309¹⁶ ≡ 583⋅583=339889 ≡ 753 mod 757

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

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

127 = 64+32+16+8+4+2+1

289¹²⁷

= 289^{64+32+16+8+4+2+1}

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

≡ 138 ⋅ 309 ⋅ 440 ⋅ 490 ⋅ 392 ⋅ 161 ⋅ 289 mod 521
≡ 42642 ⋅ 440 ⋅ 490 ⋅ 392 ⋅ 161 ⋅ 289 mod 521 ≡ 441 ⋅ 440 ⋅ 490 ⋅ 392 ⋅ 161 ⋅ 289 mod 521
≡ 194040 ⋅ 490 ⋅ 392 ⋅ 161 ⋅ 289 mod 521 ≡ 228 ⋅ 490 ⋅ 392 ⋅ 161 ⋅ 289 mod 521
≡ 111720 ⋅ 392 ⋅ 161 ⋅ 289 mod 521 ≡ 226 ⋅ 392 ⋅ 161 ⋅ 289 mod 521
≡ 88592 ⋅ 161 ⋅ 289 mod 521 ≡ 22 ⋅ 161 ⋅ 289 mod 521
≡ 3542 ⋅ 289 mod 521 ≡ 416 ⋅ 289 mod 521
≡ 120224 mod 521 ≡ 394 mod 521

Es gilt also: 289¹²⁷ ≡ 394 mod 521

Berechnung des größten gemeinsamen Teilers von 67 und 40

=>67	= 1⋅40 + 27
=>40	= 1⋅27 + 13
=>27	= 2⋅13 + 1
=>13	= 13⋅1 + 0

also gilt: ggt(67,40)=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= 27-2⋅13
13= 40-1⋅27	eingesetzt in die Zeile drüber:	1	= 1⋅27 -2⋅(40 -1⋅ 27) = 1⋅27 -2⋅40 +2⋅ 27) = -2⋅40 +3⋅ 27 (=1)
27= 67-1⋅40	eingesetzt in die Zeile drüber:	1	= -2⋅40 +3⋅(67 -1⋅ 40) = -2⋅40 +3⋅67 -3⋅ 40) = 3⋅67 -5⋅ 40 (=1)

Es gilt also: ggt(67,40)=1 = 3⋅67 -5⋅40

oder wenn man 3⋅67 auf die linke Seite bringt:

1 -3⋅67 = -5⋅40

-5⋅40 = -3⋅67 + 1 |+67⋅40

-5⋅40 + 67⋅40 = -3⋅67 + 67⋅40 + 1

(-5 + 67) ⋅ 40 = (-3 + 40) ⋅ 67 + 1

62⋅40 = 37⋅67 + 1

Es gilt also: 62⋅40 = 37⋅67 +1

Somit 62⋅40 = 1 mod 67

62 ist also das Inverse von 40 mod 67