Um längere Rechnungen zu vermeiden, rechnen wir:

(3607 + 18000) mod 9 ≡ (3607 mod 9 + 18000 mod 9) mod 9.

3607 mod 9 ≡ 7 mod 9 kann man relativ leicht bestimmen, weil ja 3607 = 3600+7 = 9 ⋅ 400 +7.

18000 mod 9 ≡ 0 mod 9 kann man relativ leicht bestimmen, weil ja 18000 = 18000+0 = 9 ⋅ 2000 +0.

Somit gilt:

(3607 + 18000) mod 9 ≡ (7 + 0) mod 9 ≡ 7 mod 9.

Um längere Rechnungen zu vermeiden, rechnen wir:

(15 ⋅ 83) mod 9 ≡ (15 mod 9 ⋅ 83 mod 9) mod 9.

15 mod 9 ≡ 6 mod 9 kann man relativ leicht bestimmen, weil ja 15 = 9 + 6 = 1 ⋅ 9 + 6 ist.

83 mod 9 ≡ 2 mod 9 kann man relativ leicht bestimmen, weil ja 83 = 81 + 2 = 9 ⋅ 9 + 2 ist.

Somit gilt:

(15 ⋅ 83) mod 9 ≡ (6 ⋅ 2) mod 9 ≡ 12 mod 9 ≡ 3 mod 9.

Die 32 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: 681¹=681

2: 681²=681¹⁺¹=681¹⋅681¹ ≡ 681⋅681=463761 ≡ 964 mod 991

4: 681⁴=681²⁺²=681²⋅681² ≡ 964⋅964=929296 ≡ 729 mod 991

8: 681⁸=681⁴⁺⁴=681⁴⋅681⁴ ≡ 729⋅729=531441 ≡ 265 mod 991

16: 681¹⁶=681⁸⁺⁸=681⁸⋅681⁸ ≡ 265⋅265=70225 ≡ 855 mod 991

32: 681³²=681¹⁶⁺¹⁶=681¹⁶⋅681¹⁶ ≡ 855⋅855=731025 ≡ 658 mod 991

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

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

179 = 128+32+16+2+1

801¹⁷⁹

= 801^{128+32+16+2+1}

= 801¹²⁸⋅801³²⋅801¹⁶⋅801²⋅801¹

≡ 293 ⋅ 262 ⋅ 712 ⋅ 145 ⋅ 801 mod 853
≡ 76766 ⋅ 712 ⋅ 145 ⋅ 801 mod 853 ≡ 849 ⋅ 712 ⋅ 145 ⋅ 801 mod 853
≡ 604488 ⋅ 145 ⋅ 801 mod 853 ≡ 564 ⋅ 145 ⋅ 801 mod 853
≡ 81780 ⋅ 801 mod 853 ≡ 745 ⋅ 801 mod 853
≡ 596745 mod 853 ≡ 498 mod 853

Es gilt also: 801¹⁷⁹ ≡ 498 mod 853

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

=>67	= 2⋅30 + 7
=>30	= 4⋅7 + 2
=>7	= 3⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(67,30)=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= 7-3⋅2
2= 30-4⋅7	eingesetzt in die Zeile drüber:	1	= 1⋅7 -3⋅(30 -4⋅ 7) = 1⋅7 -3⋅30 +12⋅ 7) = -3⋅30 +13⋅ 7 (=1)
7= 67-2⋅30	eingesetzt in die Zeile drüber:	1	= -3⋅30 +13⋅(67 -2⋅ 30) = -3⋅30 +13⋅67 -26⋅ 30) = 13⋅67 -29⋅ 30 (=1)

Es gilt also: ggt(67,30)=1 = 13⋅67 -29⋅30

oder wenn man 13⋅67 auf die linke Seite bringt:

1 -13⋅67 = -29⋅30

-29⋅30 = -13⋅67 + 1 |+67⋅30

-29⋅30 + 67⋅30 = -13⋅67 + 67⋅30 + 1

(-29 + 67) ⋅ 30 = (-13 + 30) ⋅ 67 + 1

38⋅30 = 17⋅67 + 1

Es gilt also: 38⋅30 = 17⋅67 +1

Somit 38⋅30 = 1 mod 67

38 ist also das Inverse von 30 mod 67