Um längere Rechnungen zu vermeiden, rechnen wir:

(8997 - 15003) mod 3 ≡ (8997 mod 3 - 15003 mod 3) mod 3.

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

15003 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 15003 = 15000+3 = 3 ⋅ 5000 +3.

Somit gilt:

(8997 - 15003) mod 3 ≡ (0 - 0) mod 3 ≡ 0 mod 3.

Um längere Rechnungen zu vermeiden, rechnen wir:

(54 ⋅ 26) mod 4 ≡ (54 mod 4 ⋅ 26 mod 4) mod 4.

54 mod 4 ≡ 2 mod 4 kann man relativ leicht bestimmen, weil ja 54 = 52 + 2 = 13 ⋅ 4 + 2 ist.

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

Somit gilt:

(54 ⋅ 26) mod 4 ≡ (2 ⋅ 2) mod 4 ≡ 4 mod 4 ≡ 0 mod 4.

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

2: 286²=286¹⁺¹=286¹⋅286¹ ≡ 286⋅286=81796 ≡ 389 mod 641

4: 286⁴=286²⁺²=286²⋅286² ≡ 389⋅389=151321 ≡ 45 mod 641

8: 286⁸=286⁴⁺⁴=286⁴⋅286⁴ ≡ 45⋅45=2025 ≡ 102 mod 641

16: 286¹⁶=286⁸⁺⁸=286⁸⋅286⁸ ≡ 102⋅102=10404 ≡ 148 mod 641

32: 286³²=286¹⁶⁺¹⁶=286¹⁶⋅286¹⁶ ≡ 148⋅148=21904 ≡ 110 mod 641

64: 286⁶⁴=286³²⁺³²=286³²⋅286³² ≡ 110⋅110=12100 ≡ 562 mod 641

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

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

202 = 128+64+8+2

700²⁰²

= 700^128+64+8+2

= 700¹²⁸⋅700⁶⁴⋅700⁸⋅700²

≡ 213 ⋅ 520 ⋅ 284 ⋅ 473 mod 997
≡ 110760 ⋅ 284 ⋅ 473 mod 997 ≡ 93 ⋅ 284 ⋅ 473 mod 997
≡ 26412 ⋅ 473 mod 997 ≡ 490 ⋅ 473 mod 997
≡ 231770 mod 997 ≡ 466 mod 997

Es gilt also: 700²⁰² ≡ 466 mod 997

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

=>89	= 1⋅72 + 17
=>72	= 4⋅17 + 4
=>17	= 4⋅4 + 1
=>4	= 4⋅1 + 0

also gilt: ggt(89,72)=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-4⋅4
4= 72-4⋅17	eingesetzt in die Zeile drüber:	1	= 1⋅17 -4⋅(72 -4⋅ 17) = 1⋅17 -4⋅72 +16⋅ 17) = -4⋅72 +17⋅ 17 (=1)
17= 89-1⋅72	eingesetzt in die Zeile drüber:	1	= -4⋅72 +17⋅(89 -1⋅ 72) = -4⋅72 +17⋅89 -17⋅ 72) = 17⋅89 -21⋅ 72 (=1)

Es gilt also: ggt(89,72)=1 = 17⋅89 -21⋅72

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

1 -17⋅89 = -21⋅72

-21⋅72 = -17⋅89 + 1 |+89⋅72

-21⋅72 + 89⋅72 = -17⋅89 + 89⋅72 + 1

(-21 + 89) ⋅ 72 = (-17 + 72) ⋅ 89 + 1

68⋅72 = 55⋅89 + 1

Es gilt also: 68⋅72 = 55⋅89 +1

Somit 68⋅72 = 1 mod 89

68 ist also das Inverse von 72 mod 89