Um längere Rechnungen zu vermeiden, rechnen wir:

(1608 - 78) mod 8 ≡ (1608 mod 8 - 78 mod 8) mod 8.

1608 mod 8 ≡ 0 mod 8 kann man relativ leicht bestimmen, weil ja 1608 = 1600+8 = 8 ⋅ 200 +8.

78 mod 8 ≡ 6 mod 8 kann man relativ leicht bestimmen, weil ja 78 = 80-2 = 8 ⋅ 10 -2 = 8 ⋅ 10 - 8 + 6.

Somit gilt:

(1608 - 78) mod 8 ≡ (0 - 6) mod 8 ≡ -6 mod 8 ≡ 2 mod 8.

Um längere Rechnungen zu vermeiden, rechnen wir:

(36 ⋅ 23) mod 5 ≡ (36 mod 5 ⋅ 23 mod 5) mod 5.

36 mod 5 ≡ 1 mod 5 kann man relativ leicht bestimmen, weil ja 36 = 35 + 1 = 7 ⋅ 5 + 1 ist.

23 mod 5 ≡ 3 mod 5 kann man relativ leicht bestimmen, weil ja 23 = 20 + 3 = 4 ⋅ 5 + 3 ist.

Somit gilt:

(36 ⋅ 23) mod 5 ≡ (1 ⋅ 3) mod 5 ≡ 3 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: 810¹=810

2: 810²=810¹⁺¹=810¹⋅810¹ ≡ 810⋅810=656100 ≡ 104 mod 877

4: 810⁴=810²⁺²=810²⋅810² ≡ 104⋅104=10816 ≡ 292 mod 877

8: 810⁸=810⁴⁺⁴=810⁴⋅810⁴ ≡ 292⋅292=85264 ≡ 195 mod 877

16: 810¹⁶=810⁸⁺⁸=810⁸⋅810⁸ ≡ 195⋅195=38025 ≡ 314 mod 877

32: 810³²=810¹⁶⁺¹⁶=810¹⁶⋅810¹⁶ ≡ 314⋅314=98596 ≡ 372 mod 877

64: 810⁶⁴=810³²⁺³²=810³²⋅810³² ≡ 372⋅372=138384 ≡ 695 mod 877

128: 810¹²⁸=810⁶⁴⁺⁶⁴=810⁶⁴⋅810⁶⁴ ≡ 695⋅695=483025 ≡ 675 mod 877

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

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

174 = 128+32+8+4+2

312¹⁷⁴

= 312^128+32+8+4+2

= 312¹²⁸⋅312³²⋅312⁸⋅312⁴⋅312²

≡ 307 ⋅ 80 ⋅ 780 ⋅ 305 ⋅ 244 mod 971
≡ 24560 ⋅ 780 ⋅ 305 ⋅ 244 mod 971 ≡ 285 ⋅ 780 ⋅ 305 ⋅ 244 mod 971
≡ 222300 ⋅ 305 ⋅ 244 mod 971 ≡ 912 ⋅ 305 ⋅ 244 mod 971
≡ 278160 ⋅ 244 mod 971 ≡ 454 ⋅ 244 mod 971
≡ 110776 mod 971 ≡ 82 mod 971

Es gilt also: 312¹⁷⁴ ≡ 82 mod 971

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

=>71	= 1⋅55 + 16
=>55	= 3⋅16 + 7
=>16	= 2⋅7 + 2
=>7	= 3⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(71,55)=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= 7-3⋅2
2= 16-2⋅7	eingesetzt in die Zeile drüber:	1	= 1⋅7 -3⋅(16 -2⋅ 7) = 1⋅7 -3⋅16 +6⋅ 7) = -3⋅16 +7⋅ 7 (=1)
7= 55-3⋅16	eingesetzt in die Zeile drüber:	1	= -3⋅16 +7⋅(55 -3⋅ 16) = -3⋅16 +7⋅55 -21⋅ 16) = 7⋅55 -24⋅ 16 (=1)
16= 71-1⋅55	eingesetzt in die Zeile drüber:	1	= 7⋅55 -24⋅(71 -1⋅ 55) = 7⋅55 -24⋅71 +24⋅ 55) = -24⋅71 +31⋅ 55 (=1)

Es gilt also: ggt(71,55)=1 = -24⋅71 +31⋅55

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

1 +24⋅71 = +31⋅55

Es gilt also: 31⋅55 = 24⋅71 +1

Somit 31⋅55 = 1 mod 71

31 ist also das Inverse von 55 mod 71