Um längere Rechnungen zu vermeiden, rechnen wir:

(174 + 302) mod 6 ≡ (174 mod 6 + 302 mod 6) mod 6.

174 mod 6 ≡ 0 mod 6 kann man relativ leicht bestimmen, weil ja 174 = 180-6 = 6 ⋅ 30 -6 = 6 ⋅ 30 - 6 + 0.

302 mod 6 ≡ 2 mod 6 kann man relativ leicht bestimmen, weil ja 302 = 300+2 = 6 ⋅ 50 +2.

Somit gilt:

(174 + 302) mod 6 ≡ (0 + 2) mod 6 ≡ 2 mod 6.

Um längere Rechnungen zu vermeiden, rechnen wir:

(54 ⋅ 60) mod 5 ≡ (54 mod 5 ⋅ 60 mod 5) mod 5.

54 mod 5 ≡ 4 mod 5 kann man relativ leicht bestimmen, weil ja 54 = 50 + 4 = 10 ⋅ 5 + 4 ist.

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

Somit gilt:

(54 ⋅ 60) mod 5 ≡ (4 ⋅ 0) mod 5 ≡ 0 mod 5.

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

2: 171²=171¹⁺¹=171¹⋅171¹ ≡ 171⋅171=29241 ≡ 156 mod 277

4: 171⁴=171²⁺²=171²⋅171² ≡ 156⋅156=24336 ≡ 237 mod 277

8: 171⁸=171⁴⁺⁴=171⁴⋅171⁴ ≡ 237⋅237=56169 ≡ 215 mod 277

16: 171¹⁶=171⁸⁺⁸=171⁸⋅171⁸ ≡ 215⋅215=46225 ≡ 243 mod 277

32: 171³²=171¹⁶⁺¹⁶=171¹⁶⋅171¹⁶ ≡ 243⋅243=59049 ≡ 48 mod 277

64: 171⁶⁴=171³²⁺³²=171³²⋅171³² ≡ 48⋅48=2304 ≡ 88 mod 277

128: 171¹²⁸=171⁶⁴⁺⁶⁴=171⁶⁴⋅171⁶⁴ ≡ 88⋅88=7744 ≡ 265 mod 277

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

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

184 = 128+32+16+8

160¹⁸⁴

= 160^128+32+16+8

= 160¹²⁸⋅160³²⋅160¹⁶⋅160⁸

≡ 2 ⋅ 401 ⋅ 141 ⋅ 221 mod 487
≡ 802 ⋅ 141 ⋅ 221 mod 487 ≡ 315 ⋅ 141 ⋅ 221 mod 487
≡ 44415 ⋅ 221 mod 487 ≡ 98 ⋅ 221 mod 487
≡ 21658 mod 487 ≡ 230 mod 487

Es gilt also: 160¹⁸⁴ ≡ 230 mod 487

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

=>71	= 2⋅32 + 7
=>32	= 4⋅7 + 4
=>7	= 1⋅4 + 3
=>4	= 1⋅3 + 1
=>3	= 3⋅1 + 0

also gilt: ggt(71,32)=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= 4-1⋅3
3= 7-1⋅4	eingesetzt in die Zeile drüber:	1	= 1⋅4 -1⋅(7 -1⋅ 4) = 1⋅4 -1⋅7 +1⋅ 4) = -1⋅7 +2⋅ 4 (=1)
4= 32-4⋅7	eingesetzt in die Zeile drüber:	1	= -1⋅7 +2⋅(32 -4⋅ 7) = -1⋅7 +2⋅32 -8⋅ 7) = 2⋅32 -9⋅ 7 (=1)
7= 71-2⋅32	eingesetzt in die Zeile drüber:	1	= 2⋅32 -9⋅(71 -2⋅ 32) = 2⋅32 -9⋅71 +18⋅ 32) = -9⋅71 +20⋅ 32 (=1)

Es gilt also: ggt(71,32)=1 = -9⋅71 +20⋅32

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

1 +9⋅71 = +20⋅32

Es gilt also: 20⋅32 = 9⋅71 +1

Somit 20⋅32 = 1 mod 71

20 ist also das Inverse von 32 mod 71