Um längere Rechnungen zu vermeiden, rechnen wir:

(6003 + 24002) mod 6 ≡ (6003 mod 6 + 24002 mod 6) mod 6.

6003 mod 6 ≡ 3 mod 6 kann man relativ leicht bestimmen, weil ja 6003 = 6000+3 = 6 ⋅ 1000 +3.

24002 mod 6 ≡ 2 mod 6 kann man relativ leicht bestimmen, weil ja 24002 = 24000+2 = 6 ⋅ 4000 +2.

Somit gilt:

(6003 + 24002) mod 6 ≡ (3 + 2) mod 6 ≡ 5 mod 6.

Um längere Rechnungen zu vermeiden, rechnen wir:

(58 ⋅ 44) mod 11 ≡ (58 mod 11 ⋅ 44 mod 11) mod 11.

58 mod 11 ≡ 3 mod 11 kann man relativ leicht bestimmen, weil ja 58 = 55 + 3 = 5 ⋅ 11 + 3 ist.

44 mod 11 ≡ 0 mod 11 kann man relativ leicht bestimmen, weil ja 44 = 44 + 0 = 4 ⋅ 11 + 0 ist.

Somit gilt:

(58 ⋅ 44) mod 11 ≡ (3 ⋅ 0) mod 11 ≡ 0 mod 11.

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

2: 206²=206¹⁺¹=206¹⋅206¹ ≡ 206⋅206=42436 ≡ 211 mod 563

4: 206⁴=206²⁺²=206²⋅206² ≡ 211⋅211=44521 ≡ 44 mod 563

8: 206⁸=206⁴⁺⁴=206⁴⋅206⁴ ≡ 44⋅44=1936 ≡ 247 mod 563

16: 206¹⁶=206⁸⁺⁸=206⁸⋅206⁸ ≡ 247⋅247=61009 ≡ 205 mod 563

32: 206³²=206¹⁶⁺¹⁶=206¹⁶⋅206¹⁶ ≡ 205⋅205=42025 ≡ 363 mod 563

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

264²⁵²

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

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

≡ 339 ⋅ 115 ⋅ 185 ⋅ 180 ⋅ 234 ⋅ 84 mod 379
≡ 38985 ⋅ 185 ⋅ 180 ⋅ 234 ⋅ 84 mod 379 ≡ 327 ⋅ 185 ⋅ 180 ⋅ 234 ⋅ 84 mod 379
≡ 60495 ⋅ 180 ⋅ 234 ⋅ 84 mod 379 ≡ 234 ⋅ 180 ⋅ 234 ⋅ 84 mod 379
≡ 42120 ⋅ 234 ⋅ 84 mod 379 ≡ 51 ⋅ 234 ⋅ 84 mod 379
≡ 11934 ⋅ 84 mod 379 ≡ 185 ⋅ 84 mod 379
≡ 15540 mod 379 ≡ 1 mod 379

Es gilt also: 264²⁵² ≡ 1 mod 379

Berechnung des größten gemeinsamen Teilers von 89 und 86

=>89	= 1⋅86 + 3
=>86	= 28⋅3 + 2
=>3	= 1⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(89,86)=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= 86-28⋅3	eingesetzt in die Zeile drüber:	1	= 1⋅3 -1⋅(86 -28⋅ 3) = 1⋅3 -1⋅86 +28⋅ 3) = -1⋅86 +29⋅ 3 (=1)
3= 89-1⋅86	eingesetzt in die Zeile drüber:	1	= -1⋅86 +29⋅(89 -1⋅ 86) = -1⋅86 +29⋅89 -29⋅ 86) = 29⋅89 -30⋅ 86 (=1)

Es gilt also: ggt(89,86)=1 = 29⋅89 -30⋅86

oder wenn man 29⋅89 auf die linke Seite bringt:

1 -29⋅89 = -30⋅86

-30⋅86 = -29⋅89 + 1 |+89⋅86

-30⋅86 + 89⋅86 = -29⋅89 + 89⋅86 + 1

(-30 + 89) ⋅ 86 = (-29 + 86) ⋅ 89 + 1

59⋅86 = 57⋅89 + 1

Es gilt also: 59⋅86 = 57⋅89 +1

Somit 59⋅86 = 1 mod 89

59 ist also das Inverse von 86 mod 89