Um längere Rechnungen zu vermeiden, rechnen wir:

(17995 - 1194) mod 6 ≡ (17995 mod 6 - 1194 mod 6) mod 6.

17995 mod 6 ≡ 1 mod 6 kann man relativ leicht bestimmen, weil ja 17995 = 18000-5 = 6 ⋅ 3000 -5 = 6 ⋅ 3000 - 6 + 1.

1194 mod 6 ≡ 0 mod 6 kann man relativ leicht bestimmen, weil ja 1194 = 1200-6 = 6 ⋅ 200 -6 = 6 ⋅ 200 - 6 + 0.

Somit gilt:

(17995 - 1194) mod 6 ≡ (1 - 0) mod 6 ≡ 1 mod 6.

Um längere Rechnungen zu vermeiden, rechnen wir:

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

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

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

Somit gilt:

(63 ⋅ 85) mod 7 ≡ (0 ⋅ 1) mod 7 ≡ 0 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: 184¹=184

2: 184²=184¹⁺¹=184¹⋅184¹ ≡ 184⋅184=33856 ≡ 468 mod 491

4: 184⁴=184²⁺²=184²⋅184² ≡ 468⋅468=219024 ≡ 38 mod 491

8: 184⁸=184⁴⁺⁴=184⁴⋅184⁴ ≡ 38⋅38=1444 ≡ 462 mod 491

16: 184¹⁶=184⁸⁺⁸=184⁸⋅184⁸ ≡ 462⋅462=213444 ≡ 350 mod 491

32: 184³²=184¹⁶⁺¹⁶=184¹⁶⋅184¹⁶ ≡ 350⋅350=122500 ≡ 241 mod 491

64: 184⁶⁴=184³²⁺³²=184³²⋅184³² ≡ 241⋅241=58081 ≡ 143 mod 491

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

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

239 = 128+64+32+8+4+2+1

317²³⁹

= 317^{128+64+32+8+4+2+1}

= 317¹²⁸⋅317⁶⁴⋅317³²⋅317⁸⋅317⁴⋅317²⋅317¹

≡ 254 ⋅ 544 ⋅ 296 ⋅ 841 ⋅ 878 ⋅ 719 ⋅ 317 mod 907
≡ 138176 ⋅ 296 ⋅ 841 ⋅ 878 ⋅ 719 ⋅ 317 mod 907 ≡ 312 ⋅ 296 ⋅ 841 ⋅ 878 ⋅ 719 ⋅ 317 mod 907
≡ 92352 ⋅ 841 ⋅ 878 ⋅ 719 ⋅ 317 mod 907 ≡ 745 ⋅ 841 ⋅ 878 ⋅ 719 ⋅ 317 mod 907
≡ 626545 ⋅ 878 ⋅ 719 ⋅ 317 mod 907 ≡ 715 ⋅ 878 ⋅ 719 ⋅ 317 mod 907
≡ 627770 ⋅ 719 ⋅ 317 mod 907 ≡ 126 ⋅ 719 ⋅ 317 mod 907
≡ 90594 ⋅ 317 mod 907 ≡ 801 ⋅ 317 mod 907
≡ 253917 mod 907 ≡ 864 mod 907

Es gilt also: 317²³⁹ ≡ 864 mod 907

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

=>67	= 1⋅42 + 25
=>42	= 1⋅25 + 17
=>25	= 1⋅17 + 8
=>17	= 2⋅8 + 1
=>8	= 8⋅1 + 0

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

Es gilt also: ggt(67,42)=1 = -5⋅67 +8⋅42

oder wenn man -5⋅67 auf die linke Seite bringt:

1 +5⋅67 = +8⋅42

Es gilt also: 8⋅42 = 5⋅67 +1

Somit 8⋅42 = 1 mod 67

8 ist also das Inverse von 42 mod 67