Um längere Rechnungen zu vermeiden, rechnen wir:

(178 + 89) mod 9 ≡ (178 mod 9 + 89 mod 9) mod 9.

178 mod 9 ≡ 7 mod 9 kann man relativ leicht bestimmen, weil ja 178 = 180-2 = 9 ⋅ 20 -2 = 9 ⋅ 20 - 9 + 7.

89 mod 9 ≡ 8 mod 9 kann man relativ leicht bestimmen, weil ja 89 = 90-1 = 9 ⋅ 10 -1 = 9 ⋅ 10 - 9 + 8.

Somit gilt:

(178 + 89) mod 9 ≡ (7 + 8) mod 9 ≡ 15 mod 9 ≡ 6 mod 9.

Um längere Rechnungen zu vermeiden, rechnen wir:

(16 ⋅ 40) mod 4 ≡ (16 mod 4 ⋅ 40 mod 4) mod 4.

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

40 mod 4 ≡ 0 mod 4 kann man relativ leicht bestimmen, weil ja 40 = 40 + 0 = 10 ⋅ 4 + 0 ist.

Somit gilt:

(16 ⋅ 40) mod 4 ≡ (0 ⋅ 0) mod 4 ≡ 0 mod 4.

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

2: 349²=349¹⁺¹=349¹⋅349¹ ≡ 349⋅349=121801 ≡ 451 mod 809

4: 349⁴=349²⁺²=349²⋅349² ≡ 451⋅451=203401 ≡ 342 mod 809

8: 349⁸=349⁴⁺⁴=349⁴⋅349⁴ ≡ 342⋅342=116964 ≡ 468 mod 809

16: 349¹⁶=349⁸⁺⁸=349⁸⋅349⁸ ≡ 468⋅468=219024 ≡ 594 mod 809

32: 349³²=349¹⁶⁺¹⁶=349¹⁶⋅349¹⁶ ≡ 594⋅594=352836 ≡ 112 mod 809

64: 349⁶⁴=349³²⁺³²=349³²⋅349³² ≡ 112⋅112=12544 ≡ 409 mod 809

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

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

236 = 128+64+32+8+4

657²³⁶

= 657^{128+64+32+8+4}

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

≡ 274 ⋅ 49 ⋅ 7 ⋅ 558 ⋅ 408 mod 709
≡ 13426 ⋅ 7 ⋅ 558 ⋅ 408 mod 709 ≡ 664 ⋅ 7 ⋅ 558 ⋅ 408 mod 709
≡ 4648 ⋅ 558 ⋅ 408 mod 709 ≡ 394 ⋅ 558 ⋅ 408 mod 709
≡ 219852 ⋅ 408 mod 709 ≡ 62 ⋅ 408 mod 709
≡ 25296 mod 709 ≡ 481 mod 709

Es gilt also: 657²³⁶ ≡ 481 mod 709

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

=>59	= 1⋅38 + 21
=>38	= 1⋅21 + 17
=>21	= 1⋅17 + 4
=>17	= 4⋅4 + 1
=>4	= 4⋅1 + 0

also gilt: ggt(59,38)=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-4⋅4
4= 21-1⋅17	eingesetzt in die Zeile drüber:	1	= 1⋅17 -4⋅(21 -1⋅ 17) = 1⋅17 -4⋅21 +4⋅ 17) = -4⋅21 +5⋅ 17 (=1)
17= 38-1⋅21	eingesetzt in die Zeile drüber:	1	= -4⋅21 +5⋅(38 -1⋅ 21) = -4⋅21 +5⋅38 -5⋅ 21) = 5⋅38 -9⋅ 21 (=1)
21= 59-1⋅38	eingesetzt in die Zeile drüber:	1	= 5⋅38 -9⋅(59 -1⋅ 38) = 5⋅38 -9⋅59 +9⋅ 38) = -9⋅59 +14⋅ 38 (=1)

Es gilt also: ggt(59,38)=1 = -9⋅59 +14⋅38

oder wenn man -9⋅59 auf die linke Seite bringt:

1 +9⋅59 = +14⋅38

Es gilt also: 14⋅38 = 9⋅59 +1

Somit 14⋅38 = 1 mod 59

14 ist also das Inverse von 38 mod 59