Um längere Rechnungen zu vermeiden, rechnen wir:

(122 - 897) mod 3 ≡ (122 mod 3 - 897 mod 3) mod 3.

122 mod 3 ≡ 2 mod 3 kann man relativ leicht bestimmen, weil ja 122 = 120+2 = 3 ⋅ 40 +2.

897 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 897 = 900-3 = 3 ⋅ 300 -3 = 3 ⋅ 300 - 3 + 0.

Somit gilt:

(122 - 897) mod 3 ≡ (2 - 0) mod 3 ≡ 2 mod 3.

Um längere Rechnungen zu vermeiden, rechnen wir:

(38 ⋅ 63) mod 11 ≡ (38 mod 11 ⋅ 63 mod 11) mod 11.

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

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

Somit gilt:

(38 ⋅ 63) mod 11 ≡ (5 ⋅ 8) mod 11 ≡ 40 mod 11 ≡ 7 mod 11.

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

2: 384²=384¹⁺¹=384¹⋅384¹ ≡ 384⋅384=147456 ≡ 577 mod 769

4: 384⁴=384²⁺²=384²⋅384² ≡ 577⋅577=332929 ≡ 721 mod 769

8: 384⁸=384⁴⁺⁴=384⁴⋅384⁴ ≡ 721⋅721=519841 ≡ 766 mod 769

16: 384¹⁶=384⁸⁺⁸=384⁸⋅384⁸ ≡ 766⋅766=586756 ≡ 9 mod 769

32: 384³²=384¹⁶⁺¹⁶=384¹⁶⋅384¹⁶ ≡ 9⋅9=81 ≡ 81 mod 769

64: 384⁶⁴=384³²⁺³²=384³²⋅384³² ≡ 81⋅81=6561 ≡ 409 mod 769

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

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

173 = 128+32+8+4+1

560¹⁷³

= 560^128+32+8+4+1

= 560¹²⁸⋅560³²⋅560⁸⋅560⁴⋅560¹

≡ 643 ⋅ 6 ⋅ 58 ⋅ 133 ⋅ 560 mod 653
≡ 3858 ⋅ 58 ⋅ 133 ⋅ 560 mod 653 ≡ 593 ⋅ 58 ⋅ 133 ⋅ 560 mod 653
≡ 34394 ⋅ 133 ⋅ 560 mod 653 ≡ 438 ⋅ 133 ⋅ 560 mod 653
≡ 58254 ⋅ 560 mod 653 ≡ 137 ⋅ 560 mod 653
≡ 76720 mod 653 ≡ 319 mod 653

Es gilt also: 560¹⁷³ ≡ 319 mod 653

Berechnung des größten gemeinsamen Teilers von 101 und 40

=>101	= 2⋅40 + 21
=>40	= 1⋅21 + 19
=>21	= 1⋅19 + 2
=>19	= 9⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(101,40)=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= 19-9⋅2
2= 21-1⋅19	eingesetzt in die Zeile drüber:	1	= 1⋅19 -9⋅(21 -1⋅ 19) = 1⋅19 -9⋅21 +9⋅ 19) = -9⋅21 +10⋅ 19 (=1)
19= 40-1⋅21	eingesetzt in die Zeile drüber:	1	= -9⋅21 +10⋅(40 -1⋅ 21) = -9⋅21 +10⋅40 -10⋅ 21) = 10⋅40 -19⋅ 21 (=1)
21= 101-2⋅40	eingesetzt in die Zeile drüber:	1	= 10⋅40 -19⋅(101 -2⋅ 40) = 10⋅40 -19⋅101 +38⋅ 40) = -19⋅101 +48⋅ 40 (=1)

Es gilt also: ggt(101,40)=1 = -19⋅101 +48⋅40

oder wenn man -19⋅101 auf die linke Seite bringt:

1 +19⋅101 = +48⋅40

Es gilt also: 48⋅40 = 19⋅101 +1

Somit 48⋅40 = 1 mod 101

48 ist also das Inverse von 40 mod 101