Um längere Rechnungen zu vermeiden, rechnen wir:

(2393 + 32005) mod 8 ≡ (2393 mod 8 + 32005 mod 8) mod 8.

2393 mod 8 ≡ 1 mod 8 kann man relativ leicht bestimmen, weil ja 2393 = 2400-7 = 8 ⋅ 300 -7 = 8 ⋅ 300 - 8 + 1.

32005 mod 8 ≡ 5 mod 8 kann man relativ leicht bestimmen, weil ja 32005 = 32000+5 = 8 ⋅ 4000 +5.

Somit gilt:

(2393 + 32005) mod 8 ≡ (1 + 5) mod 8 ≡ 6 mod 8.

Um längere Rechnungen zu vermeiden, rechnen wir:

(39 ⋅ 100) mod 6 ≡ (39 mod 6 ⋅ 100 mod 6) mod 6.

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

100 mod 6 ≡ 4 mod 6 kann man relativ leicht bestimmen, weil ja 100 = 96 + 4 = 16 ⋅ 6 + 4 ist.

Somit gilt:

(39 ⋅ 100) mod 6 ≡ (3 ⋅ 4) mod 6 ≡ 12 mod 6 ≡ 0 mod 6.

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

2: 238²=238¹⁺¹=238¹⋅238¹ ≡ 238⋅238=56644 ≡ 236 mod 641

4: 238⁴=238²⁺²=238²⋅238² ≡ 236⋅236=55696 ≡ 570 mod 641

8: 238⁸=238⁴⁺⁴=238⁴⋅238⁴ ≡ 570⋅570=324900 ≡ 554 mod 641

16: 238¹⁶=238⁸⁺⁸=238⁸⋅238⁸ ≡ 554⋅554=306916 ≡ 518 mod 641

32: 238³²=238¹⁶⁺¹⁶=238¹⁶⋅238¹⁶ ≡ 518⋅518=268324 ≡ 386 mod 641

64: 238⁶⁴=238³²⁺³²=238³²⋅238³² ≡ 386⋅386=148996 ≡ 284 mod 641

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

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

252 = 128+64+32+16+8+4

276²⁵²

= 276^{128+64+32+16+8+4}

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

≡ 187 ⋅ 136 ⋅ 141 ⋅ 44 ⋅ 54 ⋅ 316 mod 359
≡ 25432 ⋅ 141 ⋅ 44 ⋅ 54 ⋅ 316 mod 359 ≡ 302 ⋅ 141 ⋅ 44 ⋅ 54 ⋅ 316 mod 359
≡ 42582 ⋅ 44 ⋅ 54 ⋅ 316 mod 359 ≡ 220 ⋅ 44 ⋅ 54 ⋅ 316 mod 359
≡ 9680 ⋅ 54 ⋅ 316 mod 359 ≡ 346 ⋅ 54 ⋅ 316 mod 359
≡ 18684 ⋅ 316 mod 359 ≡ 16 ⋅ 316 mod 359
≡ 5056 mod 359 ≡ 30 mod 359

Es gilt also: 276²⁵² ≡ 30 mod 359

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