Um längere Rechnungen zu vermeiden, rechnen wir:

(172 - 909) mod 9 ≡ (172 mod 9 - 909 mod 9) mod 9.

172 mod 9 ≡ 1 mod 9 kann man relativ leicht bestimmen, weil ja 172 = 180-8 = 9 ⋅ 20 -8 = 9 ⋅ 20 - 9 + 1.

909 mod 9 ≡ 0 mod 9 kann man relativ leicht bestimmen, weil ja 909 = 900+9 = 9 ⋅ 100 +9.

Somit gilt:

(172 - 909) mod 9 ≡ (1 - 0) mod 9 ≡ 1 mod 9.

Um längere Rechnungen zu vermeiden, rechnen wir:

(15 ⋅ 33) mod 3 ≡ (15 mod 3 ⋅ 33 mod 3) mod 3.

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

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

Somit gilt:

(15 ⋅ 33) mod 3 ≡ (0 ⋅ 0) mod 3 ≡ 0 mod 3.

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

2: 370²=370¹⁺¹=370¹⋅370¹ ≡ 370⋅370=136900 ≡ 532 mod 947

4: 370⁴=370²⁺²=370²⋅370² ≡ 532⋅532=283024 ≡ 818 mod 947

8: 370⁸=370⁴⁺⁴=370⁴⋅370⁴ ≡ 818⋅818=669124 ≡ 542 mod 947

16: 370¹⁶=370⁸⁺⁸=370⁸⋅370⁸ ≡ 542⋅542=293764 ≡ 194 mod 947

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

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

222 = 128+64+16+8+4+2

540²²²

= 540^{128+64+16+8+4+2}

= 540¹²⁸⋅540⁶⁴⋅540¹⁶⋅540⁸⋅540⁴⋅540²

≡ 158 ⋅ 668 ⋅ 687 ⋅ 748 ⋅ 724 ⋅ 258 mod 823
≡ 105544 ⋅ 687 ⋅ 748 ⋅ 724 ⋅ 258 mod 823 ≡ 200 ⋅ 687 ⋅ 748 ⋅ 724 ⋅ 258 mod 823
≡ 137400 ⋅ 748 ⋅ 724 ⋅ 258 mod 823 ≡ 782 ⋅ 748 ⋅ 724 ⋅ 258 mod 823
≡ 584936 ⋅ 724 ⋅ 258 mod 823 ≡ 606 ⋅ 724 ⋅ 258 mod 823
≡ 438744 ⋅ 258 mod 823 ≡ 85 ⋅ 258 mod 823
≡ 21930 mod 823 ≡ 532 mod 823

Es gilt also: 540²²² ≡ 532 mod 823

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

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

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

Es gilt also: ggt(59,21)=1 = 5⋅59 -14⋅21

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

1 -5⋅59 = -14⋅21

-14⋅21 = -5⋅59 + 1 |+59⋅21

-14⋅21 + 59⋅21 = -5⋅59 + 59⋅21 + 1

(-14 + 59) ⋅ 21 = (-5 + 21) ⋅ 59 + 1

45⋅21 = 16⋅59 + 1

Es gilt also: 45⋅21 = 16⋅59 +1

Somit 45⋅21 = 1 mod 59

45 ist also das Inverse von 21 mod 59