Um längere Rechnungen zu vermeiden, rechnen wir:

(29998 - 301) mod 6 ≡ (29998 mod 6 - 301 mod 6) mod 6.

29998 mod 6 ≡ 4 mod 6 kann man relativ leicht bestimmen, weil ja 29998 = 30000-2 = 6 ⋅ 5000 -2 = 6 ⋅ 5000 - 6 + 4.

301 mod 6 ≡ 1 mod 6 kann man relativ leicht bestimmen, weil ja 301 = 300+1 = 6 ⋅ 50 +1.

Somit gilt:

(29998 - 301) mod 6 ≡ (4 - 1) mod 6 ≡ 3 mod 6.

Um längere Rechnungen zu vermeiden, rechnen wir:

(21 ⋅ 27) mod 6 ≡ (21 mod 6 ⋅ 27 mod 6) mod 6.

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

27 mod 6 ≡ 3 mod 6 kann man relativ leicht bestimmen, weil ja 27 = 24 + 3 = 4 ⋅ 6 + 3 ist.

Somit gilt:

(21 ⋅ 27) mod 6 ≡ (3 ⋅ 3) mod 6 ≡ 9 mod 6 ≡ 3 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: 694¹=694

2: 694²=694¹⁺¹=694¹⋅694¹ ≡ 694⋅694=481636 ≡ 18 mod 937

4: 694⁴=694²⁺²=694²⋅694² ≡ 18⋅18=324 ≡ 324 mod 937

8: 694⁸=694⁴⁺⁴=694⁴⋅694⁴ ≡ 324⋅324=104976 ≡ 32 mod 937

16: 694¹⁶=694⁸⁺⁸=694⁸⋅694⁸ ≡ 32⋅32=1024 ≡ 87 mod 937

32: 694³²=694¹⁶⁺¹⁶=694¹⁶⋅694¹⁶ ≡ 87⋅87=7569 ≡ 73 mod 937

64: 694⁶⁴=694³²⁺³²=694³²⋅694³² ≡ 73⋅73=5329 ≡ 644 mod 937

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

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

143 = 128+8+4+2+1

435¹⁴³

= 435^128+8+4+2+1

= 435¹²⁸⋅435⁸⋅435⁴⋅435²⋅435¹

≡ 291 ⋅ 104 ⋅ 345 ⋅ 317 ⋅ 435 mod 569
≡ 30264 ⋅ 345 ⋅ 317 ⋅ 435 mod 569 ≡ 107 ⋅ 345 ⋅ 317 ⋅ 435 mod 569
≡ 36915 ⋅ 317 ⋅ 435 mod 569 ≡ 499 ⋅ 317 ⋅ 435 mod 569
≡ 158183 ⋅ 435 mod 569 ≡ 1 ⋅ 435 mod 569
≡ 435 mod 569

Es gilt also: 435¹⁴³ ≡ 435 mod 569

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

=>89	= 2⋅42 + 5
=>42	= 8⋅5 + 2
=>5	= 2⋅2 + 1
=>2	= 2⋅1 + 0

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

Es gilt also: ggt(89,42)=1 = 17⋅89 -36⋅42

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

1 -17⋅89 = -36⋅42

-36⋅42 = -17⋅89 + 1 |+89⋅42

-36⋅42 + 89⋅42 = -17⋅89 + 89⋅42 + 1

(-36 + 89) ⋅ 42 = (-17 + 42) ⋅ 89 + 1

53⋅42 = 25⋅89 + 1

Es gilt also: 53⋅42 = 25⋅89 +1

Somit 53⋅42 = 1 mod 89

53 ist also das Inverse von 42 mod 89