Um längere Rechnungen zu vermeiden, rechnen wir:

(8998 - 603) mod 3 ≡ (8998 mod 3 - 603 mod 3) mod 3.

8998 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 8998 = 9000-2 = 3 ⋅ 3000 -2 = 3 ⋅ 3000 - 3 + 1.

603 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 603 = 600+3 = 3 ⋅ 200 +3.

Somit gilt:

(8998 - 603) mod 3 ≡ (1 - 0) mod 3 ≡ 1 mod 3.

Um längere Rechnungen zu vermeiden, rechnen wir:

(16 ⋅ 55) mod 5 ≡ (16 mod 5 ⋅ 55 mod 5) mod 5.

16 mod 5 ≡ 1 mod 5 kann man relativ leicht bestimmen, weil ja 16 = 15 + 1 = 3 ⋅ 5 + 1 ist.

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

Somit gilt:

(16 ⋅ 55) mod 5 ≡ (1 ⋅ 0) mod 5 ≡ 0 mod 5.

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

2: 324²=324¹⁺¹=324¹⋅324¹ ≡ 324⋅324=104976 ≡ 368 mod 467

4: 324⁴=324²⁺²=324²⋅324² ≡ 368⋅368=135424 ≡ 461 mod 467

8: 324⁸=324⁴⁺⁴=324⁴⋅324⁴ ≡ 461⋅461=212521 ≡ 36 mod 467

16: 324¹⁶=324⁸⁺⁸=324⁸⋅324⁸ ≡ 36⋅36=1296 ≡ 362 mod 467

32: 324³²=324¹⁶⁺¹⁶=324¹⁶⋅324¹⁶ ≡ 362⋅362=131044 ≡ 284 mod 467

64: 324⁶⁴=324³²⁺³²=324³²⋅324³² ≡ 284⋅284=80656 ≡ 332 mod 467

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

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

243 = 128+64+32+16+2+1

336²⁴³

= 336^{128+64+32+16+2+1}

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

≡ 949 ⋅ 755 ⋅ 42 ⋅ 767 ⋅ 897 ⋅ 336 mod 1009
≡ 716495 ⋅ 42 ⋅ 767 ⋅ 897 ⋅ 336 mod 1009 ≡ 105 ⋅ 42 ⋅ 767 ⋅ 897 ⋅ 336 mod 1009
≡ 4410 ⋅ 767 ⋅ 897 ⋅ 336 mod 1009 ≡ 374 ⋅ 767 ⋅ 897 ⋅ 336 mod 1009
≡ 286858 ⋅ 897 ⋅ 336 mod 1009 ≡ 302 ⋅ 897 ⋅ 336 mod 1009
≡ 270894 ⋅ 336 mod 1009 ≡ 482 ⋅ 336 mod 1009
≡ 161952 mod 1009 ≡ 512 mod 1009

Es gilt also: 336²⁴³ ≡ 512 mod 1009

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

=>59	= 1⋅42 + 17
=>42	= 2⋅17 + 8
=>17	= 2⋅8 + 1
=>8	= 8⋅1 + 0

also gilt: ggt(59,42)=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= 17-2⋅8
8= 42-2⋅17	eingesetzt in die Zeile drüber:	1	= 1⋅17 -2⋅(42 -2⋅ 17) = 1⋅17 -2⋅42 +4⋅ 17) = -2⋅42 +5⋅ 17 (=1)
17= 59-1⋅42	eingesetzt in die Zeile drüber:	1	= -2⋅42 +5⋅(59 -1⋅ 42) = -2⋅42 +5⋅59 -5⋅ 42) = 5⋅59 -7⋅ 42 (=1)

Es gilt also: ggt(59,42)=1 = 5⋅59 -7⋅42

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

1 -5⋅59 = -7⋅42

-7⋅42 = -5⋅59 + 1 |+59⋅42

-7⋅42 + 59⋅42 = -5⋅59 + 59⋅42 + 1

(-7 + 59) ⋅ 42 = (-5 + 42) ⋅ 59 + 1

52⋅42 = 37⋅59 + 1

Es gilt also: 52⋅42 = 37⋅59 +1

Somit 52⋅42 = 1 mod 59

52 ist also das Inverse von 42 mod 59