Um längere Rechnungen zu vermeiden, rechnen wir:

(803 - 39992) mod 8 ≡ (803 mod 8 - 39992 mod 8) mod 8.

803 mod 8 ≡ 3 mod 8 kann man relativ leicht bestimmen, weil ja 803 = 800+3 = 8 ⋅ 100 +3.

39992 mod 8 ≡ 0 mod 8 kann man relativ leicht bestimmen, weil ja 39992 = 39000+992 = 8 ⋅ 4875 +992.

Somit gilt:

(803 - 39992) mod 8 ≡ (3 - 0) mod 8 ≡ 3 mod 8.

Um längere Rechnungen zu vermeiden, rechnen wir:

(18 ⋅ 21) mod 3 ≡ (18 mod 3 ⋅ 21 mod 3) mod 3.

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

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

Somit gilt:

(18 ⋅ 21) mod 3 ≡ (0 ⋅ 0) mod 3 ≡ 0 mod 3.

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

2: 392²=392¹⁺¹=392¹⋅392¹ ≡ 392⋅392=153664 ≡ 320 mod 599

4: 392⁴=392²⁺²=392²⋅392² ≡ 320⋅320=102400 ≡ 570 mod 599

8: 392⁸=392⁴⁺⁴=392⁴⋅392⁴ ≡ 570⋅570=324900 ≡ 242 mod 599

16: 392¹⁶=392⁸⁺⁸=392⁸⋅392⁸ ≡ 242⋅242=58564 ≡ 461 mod 599

32: 392³²=392¹⁶⁺¹⁶=392¹⁶⋅392¹⁶ ≡ 461⋅461=212521 ≡ 475 mod 599

64: 392⁶⁴=392³²⁺³²=392³²⋅392³² ≡ 475⋅475=225625 ≡ 401 mod 599

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

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

107 = 64+32+8+2+1

600¹⁰⁷

= 600^64+32+8+2+1

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

≡ 256 ⋅ 16 ⋅ 617 ⋅ 361 ⋅ 600 mod 619
≡ 4096 ⋅ 617 ⋅ 361 ⋅ 600 mod 619 ≡ 382 ⋅ 617 ⋅ 361 ⋅ 600 mod 619
≡ 235694 ⋅ 361 ⋅ 600 mod 619 ≡ 474 ⋅ 361 ⋅ 600 mod 619
≡ 171114 ⋅ 600 mod 619 ≡ 270 ⋅ 600 mod 619
≡ 162000 mod 619 ≡ 441 mod 619

Es gilt also: 600¹⁰⁷ ≡ 441 mod 619

Berechnung des größten gemeinsamen Teilers von 97 und 33

=>97	= 2⋅33 + 31
=>33	= 1⋅31 + 2
=>31	= 15⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(97,33)=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= 31-15⋅2
2= 33-1⋅31	eingesetzt in die Zeile drüber:	1	= 1⋅31 -15⋅(33 -1⋅ 31) = 1⋅31 -15⋅33 +15⋅ 31) = -15⋅33 +16⋅ 31 (=1)
31= 97-2⋅33	eingesetzt in die Zeile drüber:	1	= -15⋅33 +16⋅(97 -2⋅ 33) = -15⋅33 +16⋅97 -32⋅ 33) = 16⋅97 -47⋅ 33 (=1)

Es gilt also: ggt(97,33)=1 = 16⋅97 -47⋅33

oder wenn man 16⋅97 auf die linke Seite bringt:

1 -16⋅97 = -47⋅33

-47⋅33 = -16⋅97 + 1 |+97⋅33

-47⋅33 + 97⋅33 = -16⋅97 + 97⋅33 + 1

(-47 + 97) ⋅ 33 = (-16 + 33) ⋅ 97 + 1

50⋅33 = 17⋅97 + 1

Es gilt also: 50⋅33 = 17⋅97 +1

Somit 50⋅33 = 1 mod 97

50 ist also das Inverse von 33 mod 97