Um längere Rechnungen zu vermeiden, rechnen wir:

(25003 + 498) mod 5 ≡ (25003 mod 5 + 498 mod 5) mod 5.

25003 mod 5 ≡ 3 mod 5 kann man relativ leicht bestimmen, weil ja 25003 = 25000+3 = 5 ⋅ 5000 +3.

498 mod 5 ≡ 3 mod 5 kann man relativ leicht bestimmen, weil ja 498 = 400+98 = 5 ⋅ 80 +98.

Somit gilt:

(25003 + 498) mod 5 ≡ (3 + 3) mod 5 ≡ 6 mod 5 ≡ 1 mod 5.

Um längere Rechnungen zu vermeiden, rechnen wir:

(74 ⋅ 38) mod 10 ≡ (74 mod 10 ⋅ 38 mod 10) mod 10.

74 mod 10 ≡ 4 mod 10 kann man relativ leicht bestimmen, weil ja 74 = 70 + 4 = 7 ⋅ 10 + 4 ist.

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

Somit gilt:

(74 ⋅ 38) mod 10 ≡ (4 ⋅ 8) mod 10 ≡ 32 mod 10 ≡ 2 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: 280¹=280

2: 280²=280¹⁺¹=280¹⋅280¹ ≡ 280⋅280=78400 ≡ 9 mod 283

4: 280⁴=280²⁺²=280²⋅280² ≡ 9⋅9=81 ≡ 81 mod 283

8: 280⁸=280⁴⁺⁴=280⁴⋅280⁴ ≡ 81⋅81=6561 ≡ 52 mod 283

16: 280¹⁶=280⁸⁺⁸=280⁸⋅280⁸ ≡ 52⋅52=2704 ≡ 157 mod 283

32: 280³²=280¹⁶⁺¹⁶=280¹⁶⋅280¹⁶ ≡ 157⋅157=24649 ≡ 28 mod 283

64: 280⁶⁴=280³²⁺³²=280³²⋅280³² ≡ 28⋅28=784 ≡ 218 mod 283

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

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

179 = 128+32+16+2+1

182¹⁷⁹

= 182^{128+32+16+2+1}

= 182¹²⁸⋅182³²⋅182¹⁶⋅182²⋅182¹

≡ 52 ⋅ 340 ⋅ 43 ⋅ 429 ⋅ 182 mod 503
≡ 17680 ⋅ 43 ⋅ 429 ⋅ 182 mod 503 ≡ 75 ⋅ 43 ⋅ 429 ⋅ 182 mod 503
≡ 3225 ⋅ 429 ⋅ 182 mod 503 ≡ 207 ⋅ 429 ⋅ 182 mod 503
≡ 88803 ⋅ 182 mod 503 ≡ 275 ⋅ 182 mod 503
≡ 50050 mod 503 ≡ 253 mod 503

Es gilt also: 182¹⁷⁹ ≡ 253 mod 503

Berechnung des größten gemeinsamen Teilers von 59 und 31

=>59	= 1⋅31 + 28
=>31	= 1⋅28 + 3
=>28	= 9⋅3 + 1
=>3	= 3⋅1 + 0

also gilt: ggt(59,31)=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= 28-9⋅3
3= 31-1⋅28	eingesetzt in die Zeile drüber:	1	= 1⋅28 -9⋅(31 -1⋅ 28) = 1⋅28 -9⋅31 +9⋅ 28) = -9⋅31 +10⋅ 28 (=1)
28= 59-1⋅31	eingesetzt in die Zeile drüber:	1	= -9⋅31 +10⋅(59 -1⋅ 31) = -9⋅31 +10⋅59 -10⋅ 31) = 10⋅59 -19⋅ 31 (=1)

Es gilt also: ggt(59,31)=1 = 10⋅59 -19⋅31

oder wenn man 10⋅59 auf die linke Seite bringt:

1 -10⋅59 = -19⋅31

-19⋅31 = -10⋅59 + 1 |+59⋅31

-19⋅31 + 59⋅31 = -10⋅59 + 59⋅31 + 1

(-19 + 59) ⋅ 31 = (-10 + 31) ⋅ 59 + 1

40⋅31 = 21⋅59 + 1

Es gilt also: 40⋅31 = 21⋅59 +1

Somit 40⋅31 = 1 mod 59

40 ist also das Inverse von 31 mod 59