Um längere Rechnungen zu vermeiden, rechnen wir:

(5995 - 2994) mod 6 ≡ (5995 mod 6 - 2994 mod 6) mod 6.

5995 mod 6 ≡ 1 mod 6 kann man relativ leicht bestimmen, weil ja 5995 = 6000-5 = 6 ⋅ 1000 -5 = 6 ⋅ 1000 - 6 + 1.

2994 mod 6 ≡ 0 mod 6 kann man relativ leicht bestimmen, weil ja 2994 = 3000-6 = 6 ⋅ 500 -6 = 6 ⋅ 500 - 6 + 0.

Somit gilt:

(5995 - 2994) mod 6 ≡ (1 - 0) mod 6 ≡ 1 mod 6.

Um längere Rechnungen zu vermeiden, rechnen wir:

(59 ⋅ 67) mod 9 ≡ (59 mod 9 ⋅ 67 mod 9) mod 9.

59 mod 9 ≡ 5 mod 9 kann man relativ leicht bestimmen, weil ja 59 = 54 + 5 = 6 ⋅ 9 + 5 ist.

67 mod 9 ≡ 4 mod 9 kann man relativ leicht bestimmen, weil ja 67 = 63 + 4 = 7 ⋅ 9 + 4 ist.

Somit gilt:

(59 ⋅ 67) mod 9 ≡ (5 ⋅ 4) mod 9 ≡ 20 mod 9 ≡ 2 mod 9.

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 ≡ 72 mod 1009

4: 393⁴=393²⁺²=393²⋅393² ≡ 72⋅72=5184 ≡ 139 mod 1009

8: 393⁸=393⁴⁺⁴=393⁴⋅393⁴ ≡ 139⋅139=19321 ≡ 150 mod 1009

16: 393¹⁶=393⁸⁺⁸=393⁸⋅393⁸ ≡ 150⋅150=22500 ≡ 302 mod 1009

32: 393³²=393¹⁶⁺¹⁶=393¹⁶⋅393¹⁶ ≡ 302⋅302=91204 ≡ 394 mod 1009

64: 393⁶⁴=393³²⁺³²=393³²⋅393³² ≡ 394⋅394=155236 ≡ 859 mod 1009

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

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

187 = 128+32+16+8+2+1

538¹⁸⁷

= 538^{128+32+16+8+2+1}

= 538¹²⁸⋅538³²⋅538¹⁶⋅538⁸⋅538²⋅538¹

≡ 10 ⋅ 30 ⋅ 684 ⋅ 508 ⋅ 270 ⋅ 538 mod 757
≡ 300 ⋅ 684 ⋅ 508 ⋅ 270 ⋅ 538 mod 757
≡ 205200 ⋅ 508 ⋅ 270 ⋅ 538 mod 757 ≡ 53 ⋅ 508 ⋅ 270 ⋅ 538 mod 757
≡ 26924 ⋅ 270 ⋅ 538 mod 757 ≡ 429 ⋅ 270 ⋅ 538 mod 757
≡ 115830 ⋅ 538 mod 757 ≡ 9 ⋅ 538 mod 757
≡ 4842 mod 757 ≡ 300 mod 757

Es gilt also: 538¹⁸⁷ ≡ 300 mod 757

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

=>59	= 1⋅55 + 4
=>55	= 13⋅4 + 3
=>4	= 1⋅3 + 1
=>3	= 3⋅1 + 0

also gilt: ggt(59,55)=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= 4-1⋅3
3= 55-13⋅4	eingesetzt in die Zeile drüber:	1	= 1⋅4 -1⋅(55 -13⋅ 4) = 1⋅4 -1⋅55 +13⋅ 4) = -1⋅55 +14⋅ 4 (=1)
4= 59-1⋅55	eingesetzt in die Zeile drüber:	1	= -1⋅55 +14⋅(59 -1⋅ 55) = -1⋅55 +14⋅59 -14⋅ 55) = 14⋅59 -15⋅ 55 (=1)

Es gilt also: ggt(59,55)=1 = 14⋅59 -15⋅55

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

1 -14⋅59 = -15⋅55

-15⋅55 = -14⋅59 + 1 |+59⋅55

-15⋅55 + 59⋅55 = -14⋅59 + 59⋅55 + 1

(-15 + 59) ⋅ 55 = (-14 + 55) ⋅ 59 + 1

44⋅55 = 41⋅59 + 1

Es gilt also: 44⋅55 = 41⋅59 +1

Somit 44⋅55 = 1 mod 59

44 ist also das Inverse von 55 mod 59