Um längere Rechnungen zu vermeiden, rechnen wir:

(17993 - 36007) mod 9 ≡ (17993 mod 9 - 36007 mod 9) mod 9.

17993 mod 9 ≡ 2 mod 9 kann man relativ leicht bestimmen, weil ja 17993 = 18000-7 = 9 ⋅ 2000 -7 = 9 ⋅ 2000 - 9 + 2.

36007 mod 9 ≡ 7 mod 9 kann man relativ leicht bestimmen, weil ja 36007 = 36000+7 = 9 ⋅ 4000 +7.

Somit gilt:

(17993 - 36007) mod 9 ≡ (2 - 7) mod 9 ≡ -5 mod 9 ≡ 4 mod 9.

Um längere Rechnungen zu vermeiden, rechnen wir:

(85 ⋅ 73) mod 7 ≡ (85 mod 7 ⋅ 73 mod 7) mod 7.

85 mod 7 ≡ 1 mod 7 kann man relativ leicht bestimmen, weil ja 85 = 84 + 1 = 12 ⋅ 7 + 1 ist.

73 mod 7 ≡ 3 mod 7 kann man relativ leicht bestimmen, weil ja 73 = 70 + 3 = 10 ⋅ 7 + 3 ist.

Somit gilt:

(85 ⋅ 73) mod 7 ≡ (1 ⋅ 3) mod 7 ≡ 3 mod 7.

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

2: 393²=393¹⁺¹=393¹⋅393¹ ≡ 393⋅393=154449 ≡ 195 mod 547

4: 393⁴=393²⁺²=393²⋅393² ≡ 195⋅195=38025 ≡ 282 mod 547

8: 393⁸=393⁴⁺⁴=393⁴⋅393⁴ ≡ 282⋅282=79524 ≡ 209 mod 547

16: 393¹⁶=393⁸⁺⁸=393⁸⋅393⁸ ≡ 209⋅209=43681 ≡ 468 mod 547

32: 393³²=393¹⁶⁺¹⁶=393¹⁶⋅393¹⁶ ≡ 468⋅468=219024 ≡ 224 mod 547

64: 393⁶⁴=393³²⁺³²=393³²⋅393³² ≡ 224⋅224=50176 ≡ 399 mod 547

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

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

141 = 128+8+4+1

959¹⁴¹

= 959^128+8+4+1

= 959¹²⁸⋅959⁸⋅959⁴⋅959¹

≡ 77 ⋅ 454 ⋅ 437 ⋅ 959 mod 977
≡ 34958 ⋅ 437 ⋅ 959 mod 977 ≡ 763 ⋅ 437 ⋅ 959 mod 977
≡ 333431 ⋅ 959 mod 977 ≡ 274 ⋅ 959 mod 977
≡ 262766 mod 977 ≡ 930 mod 977

Es gilt also: 959¹⁴¹ ≡ 930 mod 977

Berechnung des größten gemeinsamen Teilers von 83 und 57

=>83	= 1⋅57 + 26
=>57	= 2⋅26 + 5
=>26	= 5⋅5 + 1
=>5	= 5⋅1 + 0

also gilt: ggt(83,57)=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= 26-5⋅5
5= 57-2⋅26	eingesetzt in die Zeile drüber:	1	= 1⋅26 -5⋅(57 -2⋅ 26) = 1⋅26 -5⋅57 +10⋅ 26) = -5⋅57 +11⋅ 26 (=1)
26= 83-1⋅57	eingesetzt in die Zeile drüber:	1	= -5⋅57 +11⋅(83 -1⋅ 57) = -5⋅57 +11⋅83 -11⋅ 57) = 11⋅83 -16⋅ 57 (=1)

Es gilt also: ggt(83,57)=1 = 11⋅83 -16⋅57

oder wenn man 11⋅83 auf die linke Seite bringt:

1 -11⋅83 = -16⋅57

-16⋅57 = -11⋅83 + 1 |+83⋅57

-16⋅57 + 83⋅57 = -11⋅83 + 83⋅57 + 1

(-16 + 83) ⋅ 57 = (-11 + 57) ⋅ 83 + 1

67⋅57 = 46⋅83 + 1

Es gilt also: 67⋅57 = 46⋅83 +1

Somit 67⋅57 = 1 mod 83

67 ist also das Inverse von 57 mod 83