Um längere Rechnungen zu vermeiden, rechnen wir:

(18003 - 1800) mod 6 ≡ (18003 mod 6 - 1800 mod 6) mod 6.

18003 mod 6 ≡ 3 mod 6 kann man relativ leicht bestimmen, weil ja 18003 = 18000+3 = 6 ⋅ 3000 +3.

1800 mod 6 ≡ 0 mod 6 kann man relativ leicht bestimmen, weil ja 1800 = 1800+0 = 6 ⋅ 300 +0.

Somit gilt:

(18003 - 1800) mod 6 ≡ (3 - 0) mod 6 ≡ 3 mod 6.

Um längere Rechnungen zu vermeiden, rechnen wir:

(16 ⋅ 35) mod 6 ≡ (16 mod 6 ⋅ 35 mod 6) mod 6.

16 mod 6 ≡ 4 mod 6 kann man relativ leicht bestimmen, weil ja 16 = 12 + 4 = 2 ⋅ 6 + 4 ist.

35 mod 6 ≡ 5 mod 6 kann man relativ leicht bestimmen, weil ja 35 = 30 + 5 = 5 ⋅ 6 + 5 ist.

Somit gilt:

(16 ⋅ 35) mod 6 ≡ (4 ⋅ 5) mod 6 ≡ 20 mod 6 ≡ 2 mod 6.

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

2: 623²=623¹⁺¹=623¹⋅623¹ ≡ 623⋅623=388129 ≡ 247 mod 653

4: 623⁴=623²⁺²=623²⋅623² ≡ 247⋅247=61009 ≡ 280 mod 653

8: 623⁸=623⁴⁺⁴=623⁴⋅623⁴ ≡ 280⋅280=78400 ≡ 40 mod 653

16: 623¹⁶=623⁸⁺⁸=623⁸⋅623⁸ ≡ 40⋅40=1600 ≡ 294 mod 653

32: 623³²=623¹⁶⁺¹⁶=623¹⁶⋅623¹⁶ ≡ 294⋅294=86436 ≡ 240 mod 653

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

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

182 = 128+32+16+4+2

262¹⁸²

= 262^{128+32+16+4+2}

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

≡ 178 ⋅ 145 ⋅ 318 ⋅ 156 ⋅ 347 mod 419
≡ 25810 ⋅ 318 ⋅ 156 ⋅ 347 mod 419 ≡ 251 ⋅ 318 ⋅ 156 ⋅ 347 mod 419
≡ 79818 ⋅ 156 ⋅ 347 mod 419 ≡ 208 ⋅ 156 ⋅ 347 mod 419
≡ 32448 ⋅ 347 mod 419 ≡ 185 ⋅ 347 mod 419
≡ 64195 mod 419 ≡ 88 mod 419

Es gilt also: 262¹⁸² ≡ 88 mod 419

Berechnung des größten gemeinsamen Teilers von 89 und 31

=>89	= 2⋅31 + 27
=>31	= 1⋅27 + 4
=>27	= 6⋅4 + 3
=>4	= 1⋅3 + 1
=>3	= 3⋅1 + 0

also gilt: ggt(89,31)=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= 27-6⋅4	eingesetzt in die Zeile drüber:	1	= 1⋅4 -1⋅(27 -6⋅ 4) = 1⋅4 -1⋅27 +6⋅ 4) = -1⋅27 +7⋅ 4 (=1)
4= 31-1⋅27	eingesetzt in die Zeile drüber:	1	= -1⋅27 +7⋅(31 -1⋅ 27) = -1⋅27 +7⋅31 -7⋅ 27) = 7⋅31 -8⋅ 27 (=1)
27= 89-2⋅31	eingesetzt in die Zeile drüber:	1	= 7⋅31 -8⋅(89 -2⋅ 31) = 7⋅31 -8⋅89 +16⋅ 31) = -8⋅89 +23⋅ 31 (=1)

Es gilt also: ggt(89,31)=1 = -8⋅89 +23⋅31

oder wenn man -8⋅89 auf die linke Seite bringt:

1 +8⋅89 = +23⋅31

Es gilt also: 23⋅31 = 8⋅89 +1

Somit 23⋅31 = 1 mod 89

23 ist also das Inverse von 31 mod 89