Um längere Rechnungen zu vermeiden, rechnen wir:

(303 + 2394) mod 6 ≡ (303 mod 6 + 2394 mod 6) mod 6.

303 mod 6 ≡ 3 mod 6 kann man relativ leicht bestimmen, weil ja 303 = 300+3 = 6 ⋅ 50 +3.

2394 mod 6 ≡ 0 mod 6 kann man relativ leicht bestimmen, weil ja 2394 = 2400-6 = 6 ⋅ 400 -6 = 6 ⋅ 400 - 6 + 0.

Somit gilt:

(303 + 2394) mod 6 ≡ (3 + 0) mod 6 ≡ 3 mod 6.

Um längere Rechnungen zu vermeiden, rechnen wir:

(100 ⋅ 60) mod 10 ≡ (100 mod 10 ⋅ 60 mod 10) mod 10.

100 mod 10 ≡ 0 mod 10 kann man relativ leicht bestimmen, weil ja 100 = 100 + 0 = 10 ⋅ 10 + 0 ist.

60 mod 10 ≡ 0 mod 10 kann man relativ leicht bestimmen, weil ja 60 = 60 + 0 = 6 ⋅ 10 + 0 ist.

Somit gilt:

(100 ⋅ 60) mod 10 ≡ (0 ⋅ 0) 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: 446¹=446

2: 446²=446¹⁺¹=446¹⋅446¹ ≡ 446⋅446=198916 ≡ 415 mod 521

4: 446⁴=446²⁺²=446²⋅446² ≡ 415⋅415=172225 ≡ 295 mod 521

8: 446⁸=446⁴⁺⁴=446⁴⋅446⁴ ≡ 295⋅295=87025 ≡ 18 mod 521

16: 446¹⁶=446⁸⁺⁸=446⁸⋅446⁸ ≡ 18⋅18=324 ≡ 324 mod 521

32: 446³²=446¹⁶⁺¹⁶=446¹⁶⋅446¹⁶ ≡ 324⋅324=104976 ≡ 255 mod 521

64: 446⁶⁴=446³²⁺³²=446³²⋅446³² ≡ 255⋅255=65025 ≡ 421 mod 521

128: 446¹²⁸=446⁶⁴⁺⁶⁴=446⁶⁴⋅446⁶⁴ ≡ 421⋅421=177241 ≡ 101 mod 521

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

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

77 = 64+8+4+1

433⁷⁷

= 433^64+8+4+1

= 433⁶⁴⋅433⁸⋅433⁴⋅433¹

≡ 55 ⋅ 14 ⋅ 280 ⋅ 433 mod 509
≡ 770 ⋅ 280 ⋅ 433 mod 509 ≡ 261 ⋅ 280 ⋅ 433 mod 509
≡ 73080 ⋅ 433 mod 509 ≡ 293 ⋅ 433 mod 509
≡ 126869 mod 509 ≡ 128 mod 509

Es gilt also: 433⁷⁷ ≡ 128 mod 509

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

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

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

Es gilt also: ggt(71,25)=1 = 6⋅71 -17⋅25

oder wenn man 6⋅71 auf die linke Seite bringt:

1 -6⋅71 = -17⋅25

-17⋅25 = -6⋅71 + 1 |+71⋅25

-17⋅25 + 71⋅25 = -6⋅71 + 71⋅25 + 1

(-17 + 71) ⋅ 25 = (-6 + 25) ⋅ 71 + 1

54⋅25 = 19⋅71 + 1

Es gilt also: 54⋅25 = 19⋅71 +1

Somit 54⋅25 = 1 mod 71

54 ist also das Inverse von 25 mod 71