Um längere Rechnungen zu vermeiden, rechnen wir:

(189 + 4507) mod 9 ≡ (189 mod 9 + 4507 mod 9) mod 9.

189 mod 9 ≡ 0 mod 9 kann man relativ leicht bestimmen, weil ja 189 = 180+9 = 9 ⋅ 20 +9.

4507 mod 9 ≡ 7 mod 9 kann man relativ leicht bestimmen, weil ja 4507 = 4500+7 = 9 ⋅ 500 +7.

Somit gilt:

(189 + 4507) mod 9 ≡ (0 + 7) mod 9 ≡ 7 mod 9.

Um längere Rechnungen zu vermeiden, rechnen wir:

(99 ⋅ 18) mod 6 ≡ (99 mod 6 ⋅ 18 mod 6) mod 6.

99 mod 6 ≡ 3 mod 6 kann man relativ leicht bestimmen, weil ja 99 = 96 + 3 = 16 ⋅ 6 + 3 ist.

18 mod 6 ≡ 0 mod 6 kann man relativ leicht bestimmen, weil ja 18 = 18 + 0 = 3 ⋅ 6 + 0 ist.

Somit gilt:

(99 ⋅ 18) mod 6 ≡ (3 ⋅ 0) mod 6 ≡ 0 mod 6.

Die 16 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: 269¹=269

2: 269²=269¹⁺¹=269¹⋅269¹ ≡ 269⋅269=72361 ≡ 370 mod 421

4: 269⁴=269²⁺²=269²⋅269² ≡ 370⋅370=136900 ≡ 75 mod 421

8: 269⁸=269⁴⁺⁴=269⁴⋅269⁴ ≡ 75⋅75=5625 ≡ 152 mod 421

16: 269¹⁶=269⁸⁺⁸=269⁸⋅269⁸ ≡ 152⋅152=23104 ≡ 370 mod 421

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

182¹⁸⁷

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

= 182¹²⁸⋅182³²⋅182¹⁶⋅182⁸⋅182²⋅182¹

≡ 90 ⋅ 278 ⋅ 97 ⋅ 293 ⋅ 173 ⋅ 182 mod 397
≡ 25020 ⋅ 97 ⋅ 293 ⋅ 173 ⋅ 182 mod 397 ≡ 9 ⋅ 97 ⋅ 293 ⋅ 173 ⋅ 182 mod 397
≡ 873 ⋅ 293 ⋅ 173 ⋅ 182 mod 397 ≡ 79 ⋅ 293 ⋅ 173 ⋅ 182 mod 397
≡ 23147 ⋅ 173 ⋅ 182 mod 397 ≡ 121 ⋅ 173 ⋅ 182 mod 397
≡ 20933 ⋅ 182 mod 397 ≡ 289 ⋅ 182 mod 397
≡ 52598 mod 397 ≡ 194 mod 397

Es gilt also: 182¹⁸⁷ ≡ 194 mod 397

Berechnung des größten gemeinsamen Teilers von 61 und 19

=>61	= 3⋅19 + 4
=>19	= 4⋅4 + 3
=>4	= 1⋅3 + 1
=>3	= 3⋅1 + 0

also gilt: ggt(61,19)=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= 19-4⋅4	eingesetzt in die Zeile drüber:	1	= 1⋅4 -1⋅(19 -4⋅ 4) = 1⋅4 -1⋅19 +4⋅ 4) = -1⋅19 +5⋅ 4 (=1)
4= 61-3⋅19	eingesetzt in die Zeile drüber:	1	= -1⋅19 +5⋅(61 -3⋅ 19) = -1⋅19 +5⋅61 -15⋅ 19) = 5⋅61 -16⋅ 19 (=1)

Es gilt also: ggt(61,19)=1 = 5⋅61 -16⋅19

oder wenn man 5⋅61 auf die linke Seite bringt:

1 -5⋅61 = -16⋅19

-16⋅19 = -5⋅61 + 1 |+61⋅19

-16⋅19 + 61⋅19 = -5⋅61 + 61⋅19 + 1

(-16 + 61) ⋅ 19 = (-5 + 19) ⋅ 61 + 1

45⋅19 = 14⋅61 + 1

Es gilt also: 45⋅19 = 14⋅61 +1

Somit 45⋅19 = 1 mod 61

45 ist also das Inverse von 19 mod 61