Um längere Rechnungen zu vermeiden, rechnen wir:

(603 + 1499) mod 3 ≡ (603 mod 3 + 1499 mod 3) mod 3.

603 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 603 = 600+3 = 3 ⋅ 200 +3.

1499 mod 3 ≡ 2 mod 3 kann man relativ leicht bestimmen, weil ja 1499 = 1500-1 = 3 ⋅ 500 -1 = 3 ⋅ 500 - 3 + 2.

Somit gilt:

(603 + 1499) mod 3 ≡ (0 + 2) mod 3 ≡ 2 mod 3.

Um längere Rechnungen zu vermeiden, rechnen wir:

(64 ⋅ 64) mod 7 ≡ (64 mod 7 ⋅ 64 mod 7) mod 7.

64 mod 7 ≡ 1 mod 7 kann man relativ leicht bestimmen, weil ja 64 = 63 + 1 = 9 ⋅ 7 + 1 ist.

64 mod 7 ≡ 1 mod 7 kann man relativ leicht bestimmen, weil ja 64 = 63 + 1 = 9 ⋅ 7 + 1 ist.

Somit gilt:

(64 ⋅ 64) mod 7 ≡ (1 ⋅ 1) mod 7 ≡ 1 mod 7.

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

2: 407²=407¹⁺¹=407¹⋅407¹ ≡ 407⋅407=165649 ≡ 220 mod 557

4: 407⁴=407²⁺²=407²⋅407² ≡ 220⋅220=48400 ≡ 498 mod 557

8: 407⁸=407⁴⁺⁴=407⁴⋅407⁴ ≡ 498⋅498=248004 ≡ 139 mod 557

16: 407¹⁶=407⁸⁺⁸=407⁸⋅407⁸ ≡ 139⋅139=19321 ≡ 383 mod 557

32: 407³²=407¹⁶⁺¹⁶=407¹⁶⋅407¹⁶ ≡ 383⋅383=146689 ≡ 198 mod 557

64: 407⁶⁴=407³²⁺³²=407³²⋅407³² ≡ 198⋅198=39204 ≡ 214 mod 557

128: 407¹²⁸=407⁶⁴⁺⁶⁴=407⁶⁴⋅407⁶⁴ ≡ 214⋅214=45796 ≡ 122 mod 557

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

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

61 = 32+16+8+4+1

280⁶¹

= 280^32+16+8+4+1

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

≡ 204 ⋅ 53 ⋅ 400 ⋅ 501 ⋅ 280 mod 521
≡ 10812 ⋅ 400 ⋅ 501 ⋅ 280 mod 521 ≡ 392 ⋅ 400 ⋅ 501 ⋅ 280 mod 521
≡ 156800 ⋅ 501 ⋅ 280 mod 521 ≡ 500 ⋅ 501 ⋅ 280 mod 521
≡ 250500 ⋅ 280 mod 521 ≡ 420 ⋅ 280 mod 521
≡ 117600 mod 521 ≡ 375 mod 521

Es gilt also: 280⁶¹ ≡ 375 mod 521

Berechnung des größten gemeinsamen Teilers von 71 und 46

=>71	= 1⋅46 + 25
=>46	= 1⋅25 + 21
=>25	= 1⋅21 + 4
=>21	= 5⋅4 + 1
=>4	= 4⋅1 + 0

also gilt: ggt(71,46)=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= 21-5⋅4
4= 25-1⋅21	eingesetzt in die Zeile drüber:	1	= 1⋅21 -5⋅(25 -1⋅ 21) = 1⋅21 -5⋅25 +5⋅ 21) = -5⋅25 +6⋅ 21 (=1)
21= 46-1⋅25	eingesetzt in die Zeile drüber:	1	= -5⋅25 +6⋅(46 -1⋅ 25) = -5⋅25 +6⋅46 -6⋅ 25) = 6⋅46 -11⋅ 25 (=1)
25= 71-1⋅46	eingesetzt in die Zeile drüber:	1	= 6⋅46 -11⋅(71 -1⋅ 46) = 6⋅46 -11⋅71 +11⋅ 46) = -11⋅71 +17⋅ 46 (=1)

Es gilt also: ggt(71,46)=1 = -11⋅71 +17⋅46

oder wenn man -11⋅71 auf die linke Seite bringt:

1 +11⋅71 = +17⋅46

Es gilt also: 17⋅46 = 11⋅71 +1

Somit 17⋅46 = 1 mod 71

17 ist also das Inverse von 46 mod 71