Um längere Rechnungen zu vermeiden, rechnen wir:

(24006 - 4003) mod 8 ≡ (24006 mod 8 - 4003 mod 8) mod 8.

24006 mod 8 ≡ 6 mod 8 kann man relativ leicht bestimmen, weil ja 24006 = 24000+6 = 8 ⋅ 3000 +6.

4003 mod 8 ≡ 3 mod 8 kann man relativ leicht bestimmen, weil ja 4003 = 4000+3 = 8 ⋅ 500 +3.

Somit gilt:

(24006 - 4003) mod 8 ≡ (6 - 3) mod 8 ≡ 3 mod 8.

Um längere Rechnungen zu vermeiden, rechnen wir:

(90 ⋅ 75) mod 4 ≡ (90 mod 4 ⋅ 75 mod 4) mod 4.

90 mod 4 ≡ 2 mod 4 kann man relativ leicht bestimmen, weil ja 90 = 88 + 2 = 22 ⋅ 4 + 2 ist.

75 mod 4 ≡ 3 mod 4 kann man relativ leicht bestimmen, weil ja 75 = 72 + 3 = 18 ⋅ 4 + 3 ist.

Somit gilt:

(90 ⋅ 75) mod 4 ≡ (2 ⋅ 3) mod 4 ≡ 6 mod 4 ≡ 2 mod 4.

Die 32 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: 287¹=287

2: 287²=287¹⁺¹=287¹⋅287¹ ≡ 287⋅287=82369 ≡ 120 mod 353

4: 287⁴=287²⁺²=287²⋅287² ≡ 120⋅120=14400 ≡ 280 mod 353

8: 287⁸=287⁴⁺⁴=287⁴⋅287⁴ ≡ 280⋅280=78400 ≡ 34 mod 353

16: 287¹⁶=287⁸⁺⁸=287⁸⋅287⁸ ≡ 34⋅34=1156 ≡ 97 mod 353

32: 287³²=287¹⁶⁺¹⁶=287¹⁶⋅287¹⁶ ≡ 97⋅97=9409 ≡ 231 mod 353

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

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

254 = 128+64+32+16+8+4+2

332²⁵⁴

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

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

≡ 365 ⋅ 157 ⋅ 422 ⋅ 319 ⋅ 188 ⋅ 144 ⋅ 12 mod 467
≡ 57305 ⋅ 422 ⋅ 319 ⋅ 188 ⋅ 144 ⋅ 12 mod 467 ≡ 331 ⋅ 422 ⋅ 319 ⋅ 188 ⋅ 144 ⋅ 12 mod 467
≡ 139682 ⋅ 319 ⋅ 188 ⋅ 144 ⋅ 12 mod 467 ≡ 49 ⋅ 319 ⋅ 188 ⋅ 144 ⋅ 12 mod 467
≡ 15631 ⋅ 188 ⋅ 144 ⋅ 12 mod 467 ≡ 220 ⋅ 188 ⋅ 144 ⋅ 12 mod 467
≡ 41360 ⋅ 144 ⋅ 12 mod 467 ≡ 264 ⋅ 144 ⋅ 12 mod 467
≡ 38016 ⋅ 12 mod 467 ≡ 189 ⋅ 12 mod 467
≡ 2268 mod 467 ≡ 400 mod 467

Es gilt also: 332²⁵⁴ ≡ 400 mod 467

Berechnung des größten gemeinsamen Teilers von 83 und 62

=>83	= 1⋅62 + 21
=>62	= 2⋅21 + 20
=>21	= 1⋅20 + 1
=>20	= 20⋅1 + 0

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

Es gilt also: ggt(83,62)=1 = 3⋅83 -4⋅62

oder wenn man 3⋅83 auf die linke Seite bringt:

1 -3⋅83 = -4⋅62

-4⋅62 = -3⋅83 + 1 |+83⋅62

-4⋅62 + 83⋅62 = -3⋅83 + 83⋅62 + 1

(-4 + 83) ⋅ 62 = (-3 + 62) ⋅ 83 + 1

79⋅62 = 59⋅83 + 1

Es gilt also: 79⋅62 = 59⋅83 +1

Somit 79⋅62 = 1 mod 83

79 ist also das Inverse von 62 mod 83