Um längere Rechnungen zu vermeiden, rechnen wir:

(60 - 32) mod 3 ≡ (60 mod 3 - 32 mod 3) mod 3.

60 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 60 = 60+0 = 3 ⋅ 20 +0.

32 mod 3 ≡ 2 mod 3 kann man relativ leicht bestimmen, weil ja 32 = 30+2 = 3 ⋅ 10 +2.

Somit gilt:

(60 - 32) mod 3 ≡ (0 - 2) mod 3 ≡ -2 mod 3 ≡ 1 mod 3.

Um längere Rechnungen zu vermeiden, rechnen wir:

(18 ⋅ 95) mod 10 ≡ (18 mod 10 ⋅ 95 mod 10) mod 10.

18 mod 10 ≡ 8 mod 10 kann man relativ leicht bestimmen, weil ja 18 = 10 + 8 = 1 ⋅ 10 + 8 ist.

95 mod 10 ≡ 5 mod 10 kann man relativ leicht bestimmen, weil ja 95 = 90 + 5 = 9 ⋅ 10 + 5 ist.

Somit gilt:

(18 ⋅ 95) mod 10 ≡ (8 ⋅ 5) mod 10 ≡ 40 mod 10 ≡ 0 mod 10.

Die 128 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: 605¹=605

2: 605²=605¹⁺¹=605¹⋅605¹ ≡ 605⋅605=366025 ≡ 928 mod 929

4: 605⁴=605²⁺²=605²⋅605² ≡ 928⋅928=861184 ≡ 1 mod 929

8: 605⁸=605⁴⁺⁴=605⁴⋅605⁴ ≡ 1⋅1=1 ≡ 1 mod 929

16: 605¹⁶=605⁸⁺⁸=605⁸⋅605⁸ ≡ 1⋅1=1 ≡ 1 mod 929

32: 605³²=605¹⁶⁺¹⁶=605¹⁶⋅605¹⁶ ≡ 1⋅1=1 ≡ 1 mod 929

64: 605⁶⁴=605³²⁺³²=605³²⋅605³² ≡ 1⋅1=1 ≡ 1 mod 929

128: 605¹²⁸=605⁶⁴⁺⁶⁴=605⁶⁴⋅605⁶⁴ ≡ 1⋅1=1 ≡ 1 mod 929

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

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

201 = 128+64+8+1

311²⁰¹

= 311^128+64+8+1

= 311¹²⁸⋅311⁶⁴⋅311⁸⋅311¹

≡ 718 ⋅ 763 ⋅ 278 ⋅ 311 mod 877
≡ 547834 ⋅ 278 ⋅ 311 mod 877 ≡ 586 ⋅ 278 ⋅ 311 mod 877
≡ 162908 ⋅ 311 mod 877 ≡ 663 ⋅ 311 mod 877
≡ 206193 mod 877 ≡ 98 mod 877

Es gilt also: 311²⁰¹ ≡ 98 mod 877

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

=>89	= 1⋅72 + 17
=>72	= 4⋅17 + 4
=>17	= 4⋅4 + 1
=>4	= 4⋅1 + 0

also gilt: ggt(89,72)=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= 72-4⋅17	eingesetzt in die Zeile drüber:	1	= 1⋅17 -4⋅(72 -4⋅ 17) = 1⋅17 -4⋅72 +16⋅ 17) = -4⋅72 +17⋅ 17 (=1)
17= 89-1⋅72	eingesetzt in die Zeile drüber:	1	= -4⋅72 +17⋅(89 -1⋅ 72) = -4⋅72 +17⋅89 -17⋅ 72) = 17⋅89 -21⋅ 72 (=1)

Es gilt also: ggt(89,72)=1 = 17⋅89 -21⋅72

oder wenn man 17⋅89 auf die linke Seite bringt:

1 -17⋅89 = -21⋅72

-21⋅72 = -17⋅89 + 1 |+89⋅72

-21⋅72 + 89⋅72 = -17⋅89 + 89⋅72 + 1

(-21 + 89) ⋅ 72 = (-17 + 72) ⋅ 89 + 1

68⋅72 = 55⋅89 + 1

Es gilt also: 68⋅72 = 55⋅89 +1

Somit 68⋅72 = 1 mod 89

68 ist also das Inverse von 72 mod 89