Um längere Rechnungen zu vermeiden, rechnen wir:

(3000 - 5998) mod 3 ≡ (3000 mod 3 - 5998 mod 3) mod 3.

3000 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 3000 = 3000+0 = 3 ⋅ 1000 +0.

5998 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 5998 = 6000-2 = 3 ⋅ 2000 -2 = 3 ⋅ 2000 - 3 + 1.

Somit gilt:

(3000 - 5998) mod 3 ≡ (0 - 1) mod 3 ≡ -1 mod 3 ≡ 2 mod 3.

Um längere Rechnungen zu vermeiden, rechnen wir:

(63 ⋅ 77) mod 11 ≡ (63 mod 11 ⋅ 77 mod 11) mod 11.

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

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

Somit gilt:

(63 ⋅ 77) mod 11 ≡ (8 ⋅ 0) mod 11 ≡ 0 mod 11.

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

2: 382²=382¹⁺¹=382¹⋅382¹ ≡ 382⋅382=145924 ≡ 308 mod 479

4: 382⁴=382²⁺²=382²⋅382² ≡ 308⋅308=94864 ≡ 22 mod 479

8: 382⁸=382⁴⁺⁴=382⁴⋅382⁴ ≡ 22⋅22=484 ≡ 5 mod 479

16: 382¹⁶=382⁸⁺⁸=382⁸⋅382⁸ ≡ 5⋅5=25 ≡ 25 mod 479

32: 382³²=382¹⁶⁺¹⁶=382¹⁶⋅382¹⁶ ≡ 25⋅25=625 ≡ 146 mod 479

64: 382⁶⁴=382³²⁺³²=382³²⋅382³² ≡ 146⋅146=21316 ≡ 240 mod 479

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

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

159 = 128+16+8+4+2+1

527¹⁵⁹

= 527^{128+16+8+4+2+1}

= 527¹²⁸⋅527¹⁶⋅527⁸⋅527⁴⋅527²⋅527¹

≡ 256 ⋅ 172 ⋅ 482 ⋅ 404 ⋅ 57 ⋅ 527 mod 569
≡ 44032 ⋅ 482 ⋅ 404 ⋅ 57 ⋅ 527 mod 569 ≡ 219 ⋅ 482 ⋅ 404 ⋅ 57 ⋅ 527 mod 569
≡ 105558 ⋅ 404 ⋅ 57 ⋅ 527 mod 569 ≡ 293 ⋅ 404 ⋅ 57 ⋅ 527 mod 569
≡ 118372 ⋅ 57 ⋅ 527 mod 569 ≡ 20 ⋅ 57 ⋅ 527 mod 569
≡ 1140 ⋅ 527 mod 569 ≡ 2 ⋅ 527 mod 569
≡ 1054 mod 569 ≡ 485 mod 569

Es gilt also: 527¹⁵⁹ ≡ 485 mod 569

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

=>89	= 2⋅39 + 11
=>39	= 3⋅11 + 6
=>11	= 1⋅6 + 5
=>6	= 1⋅5 + 1
=>5	= 5⋅1 + 0

also gilt: ggt(89,39)=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= 6-1⋅5
5= 11-1⋅6	eingesetzt in die Zeile drüber:	1	= 1⋅6 -1⋅(11 -1⋅ 6) = 1⋅6 -1⋅11 +1⋅ 6) = -1⋅11 +2⋅ 6 (=1)
6= 39-3⋅11	eingesetzt in die Zeile drüber:	1	= -1⋅11 +2⋅(39 -3⋅ 11) = -1⋅11 +2⋅39 -6⋅ 11) = 2⋅39 -7⋅ 11 (=1)
11= 89-2⋅39	eingesetzt in die Zeile drüber:	1	= 2⋅39 -7⋅(89 -2⋅ 39) = 2⋅39 -7⋅89 +14⋅ 39) = -7⋅89 +16⋅ 39 (=1)

Es gilt also: ggt(89,39)=1 = -7⋅89 +16⋅39

oder wenn man -7⋅89 auf die linke Seite bringt:

1 +7⋅89 = +16⋅39

Es gilt also: 16⋅39 = 7⋅89 +1

Somit 16⋅39 = 1 mod 89

16 ist also das Inverse von 39 mod 89