Um längere Rechnungen zu vermeiden, rechnen wir:

(8003 + 1202) mod 4 ≡ (8003 mod 4 + 1202 mod 4) mod 4.

8003 mod 4 ≡ 3 mod 4 kann man relativ leicht bestimmen, weil ja 8003 = 8000+3 = 4 ⋅ 2000 +3.

1202 mod 4 ≡ 2 mod 4 kann man relativ leicht bestimmen, weil ja 1202 = 1200+2 = 4 ⋅ 300 +2.

Somit gilt:

(8003 + 1202) mod 4 ≡ (3 + 2) mod 4 ≡ 5 mod 4 ≡ 1 mod 4.

Um längere Rechnungen zu vermeiden, rechnen wir:

(28 ⋅ 25) mod 10 ≡ (28 mod 10 ⋅ 25 mod 10) mod 10.

28 mod 10 ≡ 8 mod 10 kann man relativ leicht bestimmen, weil ja 28 = 20 + 8 = 2 ⋅ 10 + 8 ist.

25 mod 10 ≡ 5 mod 10 kann man relativ leicht bestimmen, weil ja 25 = 20 + 5 = 2 ⋅ 10 + 5 ist.

Somit gilt:

(28 ⋅ 25) mod 10 ≡ (8 ⋅ 5) mod 10 ≡ 40 mod 10 ≡ 0 mod 10.

Die 128 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: 674¹=674

2: 674²=674¹⁺¹=674¹⋅674¹ ≡ 674⋅674=454276 ≡ 819 mod 971

4: 674⁴=674²⁺²=674²⋅674² ≡ 819⋅819=670761 ≡ 771 mod 971

8: 674⁸=674⁴⁺⁴=674⁴⋅674⁴ ≡ 771⋅771=594441 ≡ 189 mod 971

16: 674¹⁶=674⁸⁺⁸=674⁸⋅674⁸ ≡ 189⋅189=35721 ≡ 765 mod 971

32: 674³²=674¹⁶⁺¹⁶=674¹⁶⋅674¹⁶ ≡ 765⋅765=585225 ≡ 683 mod 971

64: 674⁶⁴=674³²⁺³²=674³²⋅674³² ≡ 683⋅683=466489 ≡ 409 mod 971

128: 674¹²⁸=674⁶⁴⁺⁶⁴=674⁶⁴⋅674⁶⁴ ≡ 409⋅409=167281 ≡ 269 mod 971

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

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

240 = 128+64+32+16

342²⁴⁰

= 342^128+64+32+16

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

≡ 470 ⋅ 285 ⋅ 431 ⋅ 405 mod 521
≡ 133950 ⋅ 431 ⋅ 405 mod 521 ≡ 53 ⋅ 431 ⋅ 405 mod 521
≡ 22843 ⋅ 405 mod 521 ≡ 440 ⋅ 405 mod 521
≡ 178200 mod 521 ≡ 18 mod 521

Es gilt also: 342²⁴⁰ ≡ 18 mod 521

Berechnung des größten gemeinsamen Teilers von 59 und 35

=>59	= 1⋅35 + 24
=>35	= 1⋅24 + 11
=>24	= 2⋅11 + 2
=>11	= 5⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(59,35)=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= 11-5⋅2
2= 24-2⋅11	eingesetzt in die Zeile drüber:	1	= 1⋅11 -5⋅(24 -2⋅ 11) = 1⋅11 -5⋅24 +10⋅ 11) = -5⋅24 +11⋅ 11 (=1)
11= 35-1⋅24	eingesetzt in die Zeile drüber:	1	= -5⋅24 +11⋅(35 -1⋅ 24) = -5⋅24 +11⋅35 -11⋅ 24) = 11⋅35 -16⋅ 24 (=1)
24= 59-1⋅35	eingesetzt in die Zeile drüber:	1	= 11⋅35 -16⋅(59 -1⋅ 35) = 11⋅35 -16⋅59 +16⋅ 35) = -16⋅59 +27⋅ 35 (=1)

Es gilt also: ggt(59,35)=1 = -16⋅59 +27⋅35

oder wenn man -16⋅59 auf die linke Seite bringt:

1 +16⋅59 = +27⋅35

Es gilt also: 27⋅35 = 16⋅59 +1

Somit 27⋅35 = 1 mod 59

27 ist also das Inverse von 35 mod 59