Um längere Rechnungen zu vermeiden, rechnen wir:

(297 - 600) mod 3 ≡ (297 mod 3 - 600 mod 3) mod 3.

297 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 297 = 300-3 = 3 ⋅ 100 -3 = 3 ⋅ 100 - 3 + 0.

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

Somit gilt:

(297 - 600) mod 3 ≡ (0 - 0) mod 3 ≡ 0 mod 3.

Um längere Rechnungen zu vermeiden, rechnen wir:

(20 ⋅ 26) mod 4 ≡ (20 mod 4 ⋅ 26 mod 4) mod 4.

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

26 mod 4 ≡ 2 mod 4 kann man relativ leicht bestimmen, weil ja 26 = 24 + 2 = 6 ⋅ 4 + 2 ist.

Somit gilt:

(20 ⋅ 26) mod 4 ≡ (0 ⋅ 2) mod 4 ≡ 0 mod 4.

Die 64 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: 494¹=494

2: 494²=494¹⁺¹=494¹⋅494¹ ≡ 494⋅494=244036 ≡ 154 mod 797

4: 494⁴=494²⁺²=494²⋅494² ≡ 154⋅154=23716 ≡ 603 mod 797

8: 494⁸=494⁴⁺⁴=494⁴⋅494⁴ ≡ 603⋅603=363609 ≡ 177 mod 797

16: 494¹⁶=494⁸⁺⁸=494⁸⋅494⁸ ≡ 177⋅177=31329 ≡ 246 mod 797

32: 494³²=494¹⁶⁺¹⁶=494¹⁶⋅494¹⁶ ≡ 246⋅246=60516 ≡ 741 mod 797

64: 494⁶⁴=494³²⁺³²=494³²⋅494³² ≡ 741⋅741=549081 ≡ 745 mod 797

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

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

124 = 64+32+16+8+4

453¹²⁴

= 453^64+32+16+8+4

= 453⁶⁴⋅453³²⋅453¹⁶⋅453⁸⋅453⁴

≡ 515 ⋅ 68 ⋅ 194 ⋅ 437 ⋅ 555 mod 587
≡ 35020 ⋅ 194 ⋅ 437 ⋅ 555 mod 587 ≡ 387 ⋅ 194 ⋅ 437 ⋅ 555 mod 587
≡ 75078 ⋅ 437 ⋅ 555 mod 587 ≡ 529 ⋅ 437 ⋅ 555 mod 587
≡ 231173 ⋅ 555 mod 587 ≡ 482 ⋅ 555 mod 587
≡ 267510 mod 587 ≡ 425 mod 587

Es gilt also: 453¹²⁴ ≡ 425 mod 587

Berechnung des größten gemeinsamen Teilers von 83 und 45

=>83	= 1⋅45 + 38
=>45	= 1⋅38 + 7
=>38	= 5⋅7 + 3
=>7	= 2⋅3 + 1
=>3	= 3⋅1 + 0

also gilt: ggt(83,45)=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-2⋅3
3= 38-5⋅7	eingesetzt in die Zeile drüber:	1	= 1⋅7 -2⋅(38 -5⋅ 7) = 1⋅7 -2⋅38 +10⋅ 7) = -2⋅38 +11⋅ 7 (=1)
7= 45-1⋅38	eingesetzt in die Zeile drüber:	1	= -2⋅38 +11⋅(45 -1⋅ 38) = -2⋅38 +11⋅45 -11⋅ 38) = 11⋅45 -13⋅ 38 (=1)
38= 83-1⋅45	eingesetzt in die Zeile drüber:	1	= 11⋅45 -13⋅(83 -1⋅ 45) = 11⋅45 -13⋅83 +13⋅ 45) = -13⋅83 +24⋅ 45 (=1)

Es gilt also: ggt(83,45)=1 = -13⋅83 +24⋅45

oder wenn man -13⋅83 auf die linke Seite bringt:

1 +13⋅83 = +24⋅45

Es gilt also: 24⋅45 = 13⋅83 +1

Somit 24⋅45 = 1 mod 83

24 ist also das Inverse von 45 mod 83