Um längere Rechnungen zu vermeiden, rechnen wir:

(599 + 87) mod 3 ≡ (599 mod 3 + 87 mod 3) mod 3.

599 mod 3 ≡ 2 mod 3 kann man relativ leicht bestimmen, weil ja 599 = 600-1 = 3 ⋅ 200 -1 = 3 ⋅ 200 - 3 + 2.

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

Somit gilt:

(599 + 87) mod 3 ≡ (2 + 0) mod 3 ≡ 2 mod 3.

Um längere Rechnungen zu vermeiden, rechnen wir:

(69 ⋅ 87) mod 8 ≡ (69 mod 8 ⋅ 87 mod 8) mod 8.

69 mod 8 ≡ 5 mod 8 kann man relativ leicht bestimmen, weil ja 69 = 64 + 5 = 8 ⋅ 8 + 5 ist.

87 mod 8 ≡ 7 mod 8 kann man relativ leicht bestimmen, weil ja 87 = 80 + 7 = 10 ⋅ 8 + 7 ist.

Somit gilt:

(69 ⋅ 87) mod 8 ≡ (5 ⋅ 7) mod 8 ≡ 35 mod 8 ≡ 3 mod 8.

Die 32 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: 190¹=190

2: 190²=190¹⁺¹=190¹⋅190¹ ≡ 190⋅190=36100 ≡ 279 mod 317

4: 190⁴=190²⁺²=190²⋅190² ≡ 279⋅279=77841 ≡ 176 mod 317

8: 190⁸=190⁴⁺⁴=190⁴⋅190⁴ ≡ 176⋅176=30976 ≡ 227 mod 317

16: 190¹⁶=190⁸⁺⁸=190⁸⋅190⁸ ≡ 227⋅227=51529 ≡ 175 mod 317

32: 190³²=190¹⁶⁺¹⁶=190¹⁶⋅190¹⁶ ≡ 175⋅175=30625 ≡ 193 mod 317

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

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

109 = 64+32+8+4+1

358¹⁰⁹

= 358^64+32+8+4+1

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

≡ 536 ⋅ 185 ⋅ 178 ⋅ 222 ⋅ 358 mod 571
≡ 99160 ⋅ 178 ⋅ 222 ⋅ 358 mod 571 ≡ 377 ⋅ 178 ⋅ 222 ⋅ 358 mod 571
≡ 67106 ⋅ 222 ⋅ 358 mod 571 ≡ 299 ⋅ 222 ⋅ 358 mod 571
≡ 66378 ⋅ 358 mod 571 ≡ 142 ⋅ 358 mod 571
≡ 50836 mod 571 ≡ 17 mod 571

Es gilt also: 358¹⁰⁹ ≡ 17 mod 571

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

=>83	= 1⋅67 + 16
=>67	= 4⋅16 + 3
=>16	= 5⋅3 + 1
=>3	= 3⋅1 + 0

also gilt: ggt(83,67)=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= 16-5⋅3
3= 67-4⋅16	eingesetzt in die Zeile drüber:	1	= 1⋅16 -5⋅(67 -4⋅ 16) = 1⋅16 -5⋅67 +20⋅ 16) = -5⋅67 +21⋅ 16 (=1)
16= 83-1⋅67	eingesetzt in die Zeile drüber:	1	= -5⋅67 +21⋅(83 -1⋅ 67) = -5⋅67 +21⋅83 -21⋅ 67) = 21⋅83 -26⋅ 67 (=1)

Es gilt also: ggt(83,67)=1 = 21⋅83 -26⋅67

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

1 -21⋅83 = -26⋅67

-26⋅67 = -21⋅83 + 1 |+83⋅67

-26⋅67 + 83⋅67 = -21⋅83 + 83⋅67 + 1

(-26 + 83) ⋅ 67 = (-21 + 67) ⋅ 83 + 1

57⋅67 = 46⋅83 + 1

Es gilt also: 57⋅67 = 46⋅83 +1

Somit 57⋅67 = 1 mod 83

57 ist also das Inverse von 67 mod 83