Um längere Rechnungen zu vermeiden, rechnen wir:

(24999 - 2501) mod 5 ≡ (24999 mod 5 - 2501 mod 5) mod 5.

24999 mod 5 ≡ 4 mod 5 kann man relativ leicht bestimmen, weil ja 24999 = 24000+999 = 5 ⋅ 4800 +999.

2501 mod 5 ≡ 1 mod 5 kann man relativ leicht bestimmen, weil ja 2501 = 2500+1 = 5 ⋅ 500 +1.

Somit gilt:

(24999 - 2501) mod 5 ≡ (4 - 1) mod 5 ≡ 3 mod 5.

Um längere Rechnungen zu vermeiden, rechnen wir:

(39 ⋅ 63) mod 3 ≡ (39 mod 3 ⋅ 63 mod 3) mod 3.

39 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 39 = 39 + 0 = 13 ⋅ 3 + 0 ist.

63 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 63 = 63 + 0 = 21 ⋅ 3 + 0 ist.

Somit gilt:

(39 ⋅ 63) mod 3 ≡ (0 ⋅ 0) mod 3 ≡ 0 mod 3.

Die 8 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: 334¹=334

2: 334²=334¹⁺¹=334¹⋅334¹ ≡ 334⋅334=111556 ≡ 266 mod 359

4: 334⁴=334²⁺²=334²⋅334² ≡ 266⋅266=70756 ≡ 33 mod 359

8: 334⁸=334⁴⁺⁴=334⁴⋅334⁴ ≡ 33⋅33=1089 ≡ 12 mod 359

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

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

255 = 128+64+32+16+8+4+2+1

280²⁵⁵

= 280^{128+64+32+16+8+4+2+1}

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

≡ 263 ⋅ 218 ⋅ 28 ⋅ 157 ⋅ 52 ⋅ 81 ⋅ 9 ⋅ 280 mod 283
≡ 57334 ⋅ 28 ⋅ 157 ⋅ 52 ⋅ 81 ⋅ 9 ⋅ 280 mod 283 ≡ 168 ⋅ 28 ⋅ 157 ⋅ 52 ⋅ 81 ⋅ 9 ⋅ 280 mod 283
≡ 4704 ⋅ 157 ⋅ 52 ⋅ 81 ⋅ 9 ⋅ 280 mod 283 ≡ 176 ⋅ 157 ⋅ 52 ⋅ 81 ⋅ 9 ⋅ 280 mod 283
≡ 27632 ⋅ 52 ⋅ 81 ⋅ 9 ⋅ 280 mod 283 ≡ 181 ⋅ 52 ⋅ 81 ⋅ 9 ⋅ 280 mod 283
≡ 9412 ⋅ 81 ⋅ 9 ⋅ 280 mod 283 ≡ 73 ⋅ 81 ⋅ 9 ⋅ 280 mod 283
≡ 5913 ⋅ 9 ⋅ 280 mod 283 ≡ 253 ⋅ 9 ⋅ 280 mod 283
≡ 2277 ⋅ 280 mod 283 ≡ 13 ⋅ 280 mod 283
≡ 3640 mod 283 ≡ 244 mod 283

Es gilt also: 280²⁵⁵ ≡ 244 mod 283

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

=>73	= 1⋅59 + 14
=>59	= 4⋅14 + 3
=>14	= 4⋅3 + 2
=>3	= 1⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(73,59)=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= 3-1⋅2
2= 14-4⋅3	eingesetzt in die Zeile drüber:	1	= 1⋅3 -1⋅(14 -4⋅ 3) = 1⋅3 -1⋅14 +4⋅ 3) = -1⋅14 +5⋅ 3 (=1)
3= 59-4⋅14	eingesetzt in die Zeile drüber:	1	= -1⋅14 +5⋅(59 -4⋅ 14) = -1⋅14 +5⋅59 -20⋅ 14) = 5⋅59 -21⋅ 14 (=1)
14= 73-1⋅59	eingesetzt in die Zeile drüber:	1	= 5⋅59 -21⋅(73 -1⋅ 59) = 5⋅59 -21⋅73 +21⋅ 59) = -21⋅73 +26⋅ 59 (=1)

Es gilt also: ggt(73,59)=1 = -21⋅73 +26⋅59

oder wenn man -21⋅73 auf die linke Seite bringt:

1 +21⋅73 = +26⋅59

Es gilt also: 26⋅59 = 21⋅73 +1

Somit 26⋅59 = 1 mod 73

26 ist also das Inverse von 59 mod 73