Um längere Rechnungen zu vermeiden, rechnen wir:

(368 - 3603) mod 9 ≡ (368 mod 9 - 3603 mod 9) mod 9.

368 mod 9 ≡ 8 mod 9 kann man relativ leicht bestimmen, weil ja 368 = 360+8 = 9 ⋅ 40 +8.

3603 mod 9 ≡ 3 mod 9 kann man relativ leicht bestimmen, weil ja 3603 = 3600+3 = 9 ⋅ 400 +3.

Somit gilt:

(368 - 3603) mod 9 ≡ (8 - 3) mod 9 ≡ 5 mod 9.

Um längere Rechnungen zu vermeiden, rechnen wir:

(98 ⋅ 17) mod 11 ≡ (98 mod 11 ⋅ 17 mod 11) mod 11.

98 mod 11 ≡ 10 mod 11 kann man relativ leicht bestimmen, weil ja 98 = 88 + 10 = 8 ⋅ 11 + 10 ist.

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

Somit gilt:

(98 ⋅ 17) mod 11 ≡ (10 ⋅ 6) mod 11 ≡ 60 mod 11 ≡ 5 mod 11.

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

2: 301²=301¹⁺¹=301¹⋅301¹ ≡ 301⋅301=90601 ≡ 96 mod 787

4: 301⁴=301²⁺²=301²⋅301² ≡ 96⋅96=9216 ≡ 559 mod 787

8: 301⁸=301⁴⁺⁴=301⁴⋅301⁴ ≡ 559⋅559=312481 ≡ 42 mod 787

16: 301¹⁶=301⁸⁺⁸=301⁸⋅301⁸ ≡ 42⋅42=1764 ≡ 190 mod 787

32: 301³²=301¹⁶⁺¹⁶=301¹⁶⋅301¹⁶ ≡ 190⋅190=36100 ≡ 685 mod 787

64: 301⁶⁴=301³²⁺³²=301³²⋅301³² ≡ 685⋅685=469225 ≡ 173 mod 787

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

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

172 = 128+32+8+4

688¹⁷²

= 688^128+32+8+4

= 688¹²⁸⋅688³²⋅688⁸⋅688⁴

≡ 603 ⋅ 69 ⋅ 56 ⋅ 225 mod 829
≡ 41607 ⋅ 56 ⋅ 225 mod 829 ≡ 157 ⋅ 56 ⋅ 225 mod 829
≡ 8792 ⋅ 225 mod 829 ≡ 502 ⋅ 225 mod 829
≡ 112950 mod 829 ≡ 206 mod 829

Es gilt also: 688¹⁷² ≡ 206 mod 829

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

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

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

Es gilt also: ggt(83,38)=1 = 11⋅83 -24⋅38

oder wenn man 11⋅83 auf die linke Seite bringt:

1 -11⋅83 = -24⋅38

-24⋅38 = -11⋅83 + 1 |+83⋅38

-24⋅38 + 83⋅38 = -11⋅83 + 83⋅38 + 1

(-24 + 83) ⋅ 38 = (-11 + 38) ⋅ 83 + 1

59⋅38 = 27⋅83 + 1

Es gilt also: 59⋅38 = 27⋅83 +1

Somit 59⋅38 = 1 mod 83

59 ist also das Inverse von 38 mod 83