Um längere Rechnungen zu vermeiden, rechnen wir:

(1498 + 298) mod 3 ≡ (1498 mod 3 + 298 mod 3) mod 3.

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

298 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 298 = 300-2 = 3 ⋅ 100 -2 = 3 ⋅ 100 - 3 + 1.

Somit gilt:

(1498 + 298) mod 3 ≡ (1 + 1) mod 3 ≡ 2 mod 3.

Um längere Rechnungen zu vermeiden, rechnen wir:

(94 ⋅ 89) mod 5 ≡ (94 mod 5 ⋅ 89 mod 5) mod 5.

94 mod 5 ≡ 4 mod 5 kann man relativ leicht bestimmen, weil ja 94 = 90 + 4 = 18 ⋅ 5 + 4 ist.

89 mod 5 ≡ 4 mod 5 kann man relativ leicht bestimmen, weil ja 89 = 85 + 4 = 17 ⋅ 5 + 4 ist.

Somit gilt:

(94 ⋅ 89) mod 5 ≡ (4 ⋅ 4) mod 5 ≡ 16 mod 5 ≡ 1 mod 5.

Die 64 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: 400¹=400

2: 400²=400¹⁺¹=400¹⋅400¹ ≡ 400⋅400=160000 ≡ 226 mod 859

4: 400⁴=400²⁺²=400²⋅400² ≡ 226⋅226=51076 ≡ 395 mod 859

8: 400⁸=400⁴⁺⁴=400⁴⋅400⁴ ≡ 395⋅395=156025 ≡ 546 mod 859

16: 400¹⁶=400⁸⁺⁸=400⁸⋅400⁸ ≡ 546⋅546=298116 ≡ 43 mod 859

32: 400³²=400¹⁶⁺¹⁶=400¹⁶⋅400¹⁶ ≡ 43⋅43=1849 ≡ 131 mod 859

64: 400⁶⁴=400³²⁺³²=400³²⋅400³² ≡ 131⋅131=17161 ≡ 840 mod 859

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

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

107 = 64+32+8+2+1

394¹⁰⁷

= 394^64+32+8+2+1

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

≡ 433 ⋅ 267 ⋅ 327 ⋅ 499 ⋅ 394 mod 521
≡ 115611 ⋅ 327 ⋅ 499 ⋅ 394 mod 521 ≡ 470 ⋅ 327 ⋅ 499 ⋅ 394 mod 521
≡ 153690 ⋅ 499 ⋅ 394 mod 521 ≡ 516 ⋅ 499 ⋅ 394 mod 521
≡ 257484 ⋅ 394 mod 521 ≡ 110 ⋅ 394 mod 521
≡ 43340 mod 521 ≡ 97 mod 521

Es gilt also: 394¹⁰⁷ ≡ 97 mod 521

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

=>53	= 1⋅46 + 7
=>46	= 6⋅7 + 4
=>7	= 1⋅4 + 3
=>4	= 1⋅3 + 1
=>3	= 3⋅1 + 0

also gilt: ggt(53,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= 4-1⋅3
3= 7-1⋅4	eingesetzt in die Zeile drüber:	1	= 1⋅4 -1⋅(7 -1⋅ 4) = 1⋅4 -1⋅7 +1⋅ 4) = -1⋅7 +2⋅ 4 (=1)
4= 46-6⋅7	eingesetzt in die Zeile drüber:	1	= -1⋅7 +2⋅(46 -6⋅ 7) = -1⋅7 +2⋅46 -12⋅ 7) = 2⋅46 -13⋅ 7 (=1)
7= 53-1⋅46	eingesetzt in die Zeile drüber:	1	= 2⋅46 -13⋅(53 -1⋅ 46) = 2⋅46 -13⋅53 +13⋅ 46) = -13⋅53 +15⋅ 46 (=1)

Es gilt also: ggt(53,46)=1 = -13⋅53 +15⋅46

oder wenn man -13⋅53 auf die linke Seite bringt:

1 +13⋅53 = +15⋅46

Es gilt also: 15⋅46 = 13⋅53 +1

Somit 15⋅46 = 1 mod 53

15 ist also das Inverse von 46 mod 53