Um längere Rechnungen zu vermeiden, rechnen wir:

(41 + 1603) mod 4 ≡ (41 mod 4 + 1603 mod 4) mod 4.

41 mod 4 ≡ 1 mod 4 kann man relativ leicht bestimmen, weil ja 41 = 40+1 = 4 ⋅ 10 +1.

1603 mod 4 ≡ 3 mod 4 kann man relativ leicht bestimmen, weil ja 1603 = 1600+3 = 4 ⋅ 400 +3.

Somit gilt:

(41 + 1603) mod 4 ≡ (1 + 3) mod 4 ≡ 4 mod 4 ≡ 0 mod 4.

Um längere Rechnungen zu vermeiden, rechnen wir:

(44 ⋅ 80) mod 10 ≡ (44 mod 10 ⋅ 80 mod 10) mod 10.

44 mod 10 ≡ 4 mod 10 kann man relativ leicht bestimmen, weil ja 44 = 40 + 4 = 4 ⋅ 10 + 4 ist.

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

Somit gilt:

(44 ⋅ 80) mod 10 ≡ (4 ⋅ 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: 474¹=474

2: 474²=474¹⁺¹=474¹⋅474¹ ≡ 474⋅474=224676 ≡ 552 mod 983

4: 474⁴=474²⁺²=474²⋅474² ≡ 552⋅552=304704 ≡ 957 mod 983

8: 474⁸=474⁴⁺⁴=474⁴⋅474⁴ ≡ 957⋅957=915849 ≡ 676 mod 983

16: 474¹⁶=474⁸⁺⁸=474⁸⋅474⁸ ≡ 676⋅676=456976 ≡ 864 mod 983

32: 474³²=474¹⁶⁺¹⁶=474¹⁶⋅474¹⁶ ≡ 864⋅864=746496 ≡ 399 mod 983

64: 474⁶⁴=474³²⁺³²=474³²⋅474³² ≡ 399⋅399=159201 ≡ 938 mod 983

128: 474¹²⁸=474⁶⁴⁺⁶⁴=474⁶⁴⋅474⁶⁴ ≡ 938⋅938=879844 ≡ 59 mod 983

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

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

242 = 128+64+32+16+2

314²⁴²

= 314^{128+64+32+16+2}

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

≡ 703 ⋅ 538 ⋅ 835 ⋅ 832 ⋅ 583 mod 883
≡ 378214 ⋅ 835 ⋅ 832 ⋅ 583 mod 883 ≡ 290 ⋅ 835 ⋅ 832 ⋅ 583 mod 883
≡ 242150 ⋅ 832 ⋅ 583 mod 883 ≡ 208 ⋅ 832 ⋅ 583 mod 883
≡ 173056 ⋅ 583 mod 883 ≡ 871 ⋅ 583 mod 883
≡ 507793 mod 883 ≡ 68 mod 883

Es gilt also: 314²⁴² ≡ 68 mod 883

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

=>53	= 2⋅19 + 15
=>19	= 1⋅15 + 4
=>15	= 3⋅4 + 3
=>4	= 1⋅3 + 1
=>3	= 3⋅1 + 0

also gilt: ggt(53,19)=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= 15-3⋅4	eingesetzt in die Zeile drüber:	1	= 1⋅4 -1⋅(15 -3⋅ 4) = 1⋅4 -1⋅15 +3⋅ 4) = -1⋅15 +4⋅ 4 (=1)
4= 19-1⋅15	eingesetzt in die Zeile drüber:	1	= -1⋅15 +4⋅(19 -1⋅ 15) = -1⋅15 +4⋅19 -4⋅ 15) = 4⋅19 -5⋅ 15 (=1)
15= 53-2⋅19	eingesetzt in die Zeile drüber:	1	= 4⋅19 -5⋅(53 -2⋅ 19) = 4⋅19 -5⋅53 +10⋅ 19) = -5⋅53 +14⋅ 19 (=1)

Es gilt also: ggt(53,19)=1 = -5⋅53 +14⋅19

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

1 +5⋅53 = +14⋅19

Es gilt also: 14⋅19 = 5⋅53 +1

Somit 14⋅19 = 1 mod 53

14 ist also das Inverse von 19 mod 53