Um längere Rechnungen zu vermeiden, rechnen wir:

(1497 - 30) mod 3 ≡ (1497 mod 3 - 30 mod 3) mod 3.

1497 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 1497 = 1500-3 = 3 ⋅ 500 -3 = 3 ⋅ 500 - 3 + 0.

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

Somit gilt:

(1497 - 30) mod 3 ≡ (0 - 0) mod 3 ≡ 0 mod 3.

Um längere Rechnungen zu vermeiden, rechnen wir:

(99 ⋅ 20) mod 11 ≡ (99 mod 11 ⋅ 20 mod 11) mod 11.

99 mod 11 ≡ 0 mod 11 kann man relativ leicht bestimmen, weil ja 99 = 99 + 0 = 9 ⋅ 11 + 0 ist.

20 mod 11 ≡ 9 mod 11 kann man relativ leicht bestimmen, weil ja 20 = 11 + 9 = 1 ⋅ 11 + 9 ist.

Somit gilt:

(99 ⋅ 20) mod 11 ≡ (0 ⋅ 9) mod 11 ≡ 0 mod 11.

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

2: 542²=542¹⁺¹=542¹⋅542¹ ≡ 542⋅542=293764 ≡ 846 mod 877

4: 542⁴=542²⁺²=542²⋅542² ≡ 846⋅846=715716 ≡ 84 mod 877

8: 542⁸=542⁴⁺⁴=542⁴⋅542⁴ ≡ 84⋅84=7056 ≡ 40 mod 877

16: 542¹⁶=542⁸⁺⁸=542⁸⋅542⁸ ≡ 40⋅40=1600 ≡ 723 mod 877

32: 542³²=542¹⁶⁺¹⁶=542¹⁶⋅542¹⁶ ≡ 723⋅723=522729 ≡ 37 mod 877

64: 542⁶⁴=542³²⁺³²=542³²⋅542³² ≡ 37⋅37=1369 ≡ 492 mod 877

128: 542¹²⁸=542⁶⁴⁺⁶⁴=542⁶⁴⋅542⁶⁴ ≡ 492⋅492=242064 ≡ 12 mod 877

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

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

154 = 128+16+8+2

474¹⁵⁴

= 474^128+16+8+2

= 474¹²⁸⋅474¹⁶⋅474⁸⋅474²

≡ 305 ⋅ 302 ⋅ 144 ⋅ 503 mod 601
≡ 92110 ⋅ 144 ⋅ 503 mod 601 ≡ 157 ⋅ 144 ⋅ 503 mod 601
≡ 22608 ⋅ 503 mod 601 ≡ 371 ⋅ 503 mod 601
≡ 186613 mod 601 ≡ 303 mod 601

Es gilt also: 474¹⁵⁴ ≡ 303 mod 601

Berechnung des größten gemeinsamen Teilers von 59 und 31

=>59	= 1⋅31 + 28
=>31	= 1⋅28 + 3
=>28	= 9⋅3 + 1
=>3	= 3⋅1 + 0

also gilt: ggt(59,31)=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= 28-9⋅3
3= 31-1⋅28	eingesetzt in die Zeile drüber:	1	= 1⋅28 -9⋅(31 -1⋅ 28) = 1⋅28 -9⋅31 +9⋅ 28) = -9⋅31 +10⋅ 28 (=1)
28= 59-1⋅31	eingesetzt in die Zeile drüber:	1	= -9⋅31 +10⋅(59 -1⋅ 31) = -9⋅31 +10⋅59 -10⋅ 31) = 10⋅59 -19⋅ 31 (=1)

Es gilt also: ggt(59,31)=1 = 10⋅59 -19⋅31

oder wenn man 10⋅59 auf die linke Seite bringt:

1 -10⋅59 = -19⋅31

-19⋅31 = -10⋅59 + 1 |+59⋅31

-19⋅31 + 59⋅31 = -10⋅59 + 59⋅31 + 1

(-19 + 59) ⋅ 31 = (-10 + 31) ⋅ 59 + 1

40⋅31 = 21⋅59 + 1

Es gilt also: 40⋅31 = 21⋅59 +1

Somit 40⋅31 = 1 mod 59

40 ist also das Inverse von 31 mod 59