Um längere Rechnungen zu vermeiden, rechnen wir:

(1002 + 1499) mod 5 ≡ (1002 mod 5 + 1499 mod 5) mod 5.

1002 mod 5 ≡ 2 mod 5 kann man relativ leicht bestimmen, weil ja 1002 = 1000+2 = 5 ⋅ 200 +2.

1499 mod 5 ≡ 4 mod 5 kann man relativ leicht bestimmen, weil ja 1499 = 1400+99 = 5 ⋅ 280 +99.

Somit gilt:

(1002 + 1499) mod 5 ≡ (2 + 4) mod 5 ≡ 6 mod 5 ≡ 1 mod 5.

Um längere Rechnungen zu vermeiden, rechnen wir:

(63 ⋅ 83) mod 10 ≡ (63 mod 10 ⋅ 83 mod 10) mod 10.

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

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

Somit gilt:

(63 ⋅ 83) mod 10 ≡ (3 ⋅ 3) mod 10 ≡ 9 mod 10.

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

2: 101²=101¹⁺¹=101¹⋅101¹ ≡ 101⋅101=10201 ≡ 248 mod 269

4: 101⁴=101²⁺²=101²⋅101² ≡ 248⋅248=61504 ≡ 172 mod 269

8: 101⁸=101⁴⁺⁴=101⁴⋅101⁴ ≡ 172⋅172=29584 ≡ 263 mod 269

16: 101¹⁶=101⁸⁺⁸=101⁸⋅101⁸ ≡ 263⋅263=69169 ≡ 36 mod 269

32: 101³²=101¹⁶⁺¹⁶=101¹⁶⋅101¹⁶ ≡ 36⋅36=1296 ≡ 220 mod 269

64: 101⁶⁴=101³²⁺³²=101³²⋅101³² ≡ 220⋅220=48400 ≡ 249 mod 269

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

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

203 = 128+64+8+2+1

292²⁰³

= 292^128+64+8+2+1

= 292¹²⁸⋅292⁶⁴⋅292⁸⋅292²⋅292¹

≡ 151 ⋅ 271 ⋅ 320 ⋅ 108 ⋅ 292 mod 349
≡ 40921 ⋅ 320 ⋅ 108 ⋅ 292 mod 349 ≡ 88 ⋅ 320 ⋅ 108 ⋅ 292 mod 349
≡ 28160 ⋅ 108 ⋅ 292 mod 349 ≡ 240 ⋅ 108 ⋅ 292 mod 349
≡ 25920 ⋅ 292 mod 349 ≡ 94 ⋅ 292 mod 349
≡ 27448 mod 349 ≡ 226 mod 349

Es gilt also: 292²⁰³ ≡ 226 mod 349

Berechnung des größten gemeinsamen Teilers von 79 und 75

=>79	= 1⋅75 + 4
=>75	= 18⋅4 + 3
=>4	= 1⋅3 + 1
=>3	= 3⋅1 + 0

also gilt: ggt(79,75)=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= 75-18⋅4	eingesetzt in die Zeile drüber:	1	= 1⋅4 -1⋅(75 -18⋅ 4) = 1⋅4 -1⋅75 +18⋅ 4) = -1⋅75 +19⋅ 4 (=1)
4= 79-1⋅75	eingesetzt in die Zeile drüber:	1	= -1⋅75 +19⋅(79 -1⋅ 75) = -1⋅75 +19⋅79 -19⋅ 75) = 19⋅79 -20⋅ 75 (=1)

Es gilt also: ggt(79,75)=1 = 19⋅79 -20⋅75

oder wenn man 19⋅79 auf die linke Seite bringt:

1 -19⋅79 = -20⋅75

-20⋅75 = -19⋅79 + 1 |+79⋅75

-20⋅75 + 79⋅75 = -19⋅79 + 79⋅75 + 1

(-20 + 79) ⋅ 75 = (-19 + 75) ⋅ 79 + 1

59⋅75 = 56⋅79 + 1

Es gilt also: 59⋅75 = 56⋅79 +1

Somit 59⋅75 = 1 mod 79

59 ist also das Inverse von 75 mod 79