Um längere Rechnungen zu vermeiden, rechnen wir:

(180 + 18003) mod 9 ≡ (180 mod 9 + 18003 mod 9) mod 9.

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

18003 mod 9 ≡ 3 mod 9 kann man relativ leicht bestimmen, weil ja 18003 = 18000+3 = 9 ⋅ 2000 +3.

Somit gilt:

(180 + 18003) mod 9 ≡ (0 + 3) mod 9 ≡ 3 mod 9.

Um längere Rechnungen zu vermeiden, rechnen wir:

(40 ⋅ 39) mod 3 ≡ (40 mod 3 ⋅ 39 mod 3) mod 3.

40 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 40 = 39 + 1 = 13 ⋅ 3 + 1 ist.

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

Somit gilt:

(40 ⋅ 39) mod 3 ≡ (1 ⋅ 0) mod 3 ≡ 0 mod 3.

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

2: 316²=316¹⁺¹=316¹⋅316¹ ≡ 316⋅316=99856 ≡ 276 mod 383

4: 316⁴=316²⁺²=316²⋅316² ≡ 276⋅276=76176 ≡ 342 mod 383

8: 316⁸=316⁴⁺⁴=316⁴⋅316⁴ ≡ 342⋅342=116964 ≡ 149 mod 383

16: 316¹⁶=316⁸⁺⁸=316⁸⋅316⁸ ≡ 149⋅149=22201 ≡ 370 mod 383

32: 316³²=316¹⁶⁺¹⁶=316¹⁶⋅316¹⁶ ≡ 370⋅370=136900 ≡ 169 mod 383

64: 316⁶⁴=316³²⁺³²=316³²⋅316³² ≡ 169⋅169=28561 ≡ 219 mod 383

128: 316¹²⁸=316⁶⁴⁺⁶⁴=316⁶⁴⋅316⁶⁴ ≡ 219⋅219=47961 ≡ 86 mod 383

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

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

197 = 128+64+4+1

511¹⁹⁷

= 511^128+64+4+1

= 511¹²⁸⋅511⁶⁴⋅511⁴⋅511¹

≡ 531 ⋅ 101 ⋅ 961 ⋅ 511 mod 967
≡ 53631 ⋅ 961 ⋅ 511 mod 967 ≡ 446 ⋅ 961 ⋅ 511 mod 967
≡ 428606 ⋅ 511 mod 967 ≡ 225 ⋅ 511 mod 967
≡ 114975 mod 967 ≡ 869 mod 967

Es gilt also: 511¹⁹⁷ ≡ 869 mod 967

Berechnung des größten gemeinsamen Teilers von 71 und 25

=>71	= 2⋅25 + 21
=>25	= 1⋅21 + 4
=>21	= 5⋅4 + 1
=>4	= 4⋅1 + 0

also gilt: ggt(71,25)=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= 21-5⋅4
4= 25-1⋅21	eingesetzt in die Zeile drüber:	1	= 1⋅21 -5⋅(25 -1⋅ 21) = 1⋅21 -5⋅25 +5⋅ 21) = -5⋅25 +6⋅ 21 (=1)
21= 71-2⋅25	eingesetzt in die Zeile drüber:	1	= -5⋅25 +6⋅(71 -2⋅ 25) = -5⋅25 +6⋅71 -12⋅ 25) = 6⋅71 -17⋅ 25 (=1)

Es gilt also: ggt(71,25)=1 = 6⋅71 -17⋅25

oder wenn man 6⋅71 auf die linke Seite bringt:

1 -6⋅71 = -17⋅25

-17⋅25 = -6⋅71 + 1 |+71⋅25

-17⋅25 + 71⋅25 = -6⋅71 + 71⋅25 + 1

(-17 + 71) ⋅ 25 = (-6 + 25) ⋅ 71 + 1

54⋅25 = 19⋅71 + 1

Es gilt also: 54⋅25 = 19⋅71 +1

Somit 54⋅25 = 1 mod 71

54 ist also das Inverse von 25 mod 71