Um längere Rechnungen zu vermeiden, rechnen wir:

(81 + 27003) mod 9 ≡ (81 mod 9 + 27003 mod 9) mod 9.

81 mod 9 ≡ 0 mod 9 kann man relativ leicht bestimmen, weil ja 81 = 90-9 = 9 ⋅ 10 -9 = 9 ⋅ 10 - 9 + 0.

27003 mod 9 ≡ 3 mod 9 kann man relativ leicht bestimmen, weil ja 27003 = 27000+3 = 9 ⋅ 3000 +3.

Somit gilt:

(81 + 27003) mod 9 ≡ (0 + 3) mod 9 ≡ 3 mod 9.

Um längere Rechnungen zu vermeiden, rechnen wir:

(55 ⋅ 80) mod 5 ≡ (55 mod 5 ⋅ 80 mod 5) mod 5.

55 mod 5 ≡ 0 mod 5 kann man relativ leicht bestimmen, weil ja 55 = 55 + 0 = 11 ⋅ 5 + 0 ist.

80 mod 5 ≡ 0 mod 5 kann man relativ leicht bestimmen, weil ja 80 = 80 + 0 = 16 ⋅ 5 + 0 ist.

Somit gilt:

(55 ⋅ 80) mod 5 ≡ (0 ⋅ 0) mod 5 ≡ 0 mod 5.

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

2: 317²=317¹⁺¹=317¹⋅317¹ ≡ 317⋅317=100489 ≡ 388 mod 547

4: 317⁴=317²⁺²=317²⋅317² ≡ 388⋅388=150544 ≡ 119 mod 547

8: 317⁸=317⁴⁺⁴=317⁴⋅317⁴ ≡ 119⋅119=14161 ≡ 486 mod 547

16: 317¹⁶=317⁸⁺⁸=317⁸⋅317⁸ ≡ 486⋅486=236196 ≡ 439 mod 547

32: 317³²=317¹⁶⁺¹⁶=317¹⁶⋅317¹⁶ ≡ 439⋅439=192721 ≡ 177 mod 547

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

351¹⁸²

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

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

≡ 582 ⋅ 264 ⋅ 542 ⋅ 65 ⋅ 518 mod 587
≡ 153648 ⋅ 542 ⋅ 65 ⋅ 518 mod 587 ≡ 441 ⋅ 542 ⋅ 65 ⋅ 518 mod 587
≡ 239022 ⋅ 65 ⋅ 518 mod 587 ≡ 113 ⋅ 65 ⋅ 518 mod 587
≡ 7345 ⋅ 518 mod 587 ≡ 301 ⋅ 518 mod 587
≡ 155918 mod 587 ≡ 363 mod 587

Es gilt also: 351¹⁸² ≡ 363 mod 587

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

=>59	= 1⋅31 + 28
=>31	= 1⋅28 + 3
=>28	= 9⋅3 + 1
=>3	= 3⋅1 + 0

also gilt: ggt(59,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= 28-9⋅3
3= 31-1⋅28	eingesetzt in die Zeile drüber:	1	= 1⋅28 -9⋅(31 -1⋅ 28) = 1⋅28 -9⋅31 +9⋅ 28) = -9⋅31 +10⋅ 28 (=1)
28= 59-1⋅31	eingesetzt in die Zeile drüber:	1	= -9⋅31 +10⋅(59 -1⋅ 31) = -9⋅31 +10⋅59 -10⋅ 31) = 10⋅59 -19⋅ 31 (=1)

Es gilt also: ggt(59,31)=1 = 10⋅59 -19⋅31

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

1 -10⋅59 = -19⋅31

-19⋅31 = -10⋅59 + 1 |+59⋅31

-19⋅31 + 59⋅31 = -10⋅59 + 59⋅31 + 1

(-19 + 59) ⋅ 31 = (-10 + 31) ⋅ 59 + 1

40⋅31 = 21⋅59 + 1

Es gilt also: 40⋅31 = 21⋅59 +1

Somit 40⋅31 = 1 mod 59

40 ist also das Inverse von 31 mod 59