Um längere Rechnungen zu vermeiden, rechnen wir:

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

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

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

Somit gilt:

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

Um längere Rechnungen zu vermeiden, rechnen wir:

(68 ⋅ 85) mod 7 ≡ (68 mod 7 ⋅ 85 mod 7) mod 7.

68 mod 7 ≡ 5 mod 7 kann man relativ leicht bestimmen, weil ja 68 = 63 + 5 = 9 ⋅ 7 + 5 ist.

85 mod 7 ≡ 1 mod 7 kann man relativ leicht bestimmen, weil ja 85 = 84 + 1 = 12 ⋅ 7 + 1 ist.

Somit gilt:

(68 ⋅ 85) mod 7 ≡ (5 ⋅ 1) mod 7 ≡ 5 mod 7.

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

2: 363²=363¹⁺¹=363¹⋅363¹ ≡ 363⋅363=131769 ≡ 362 mod 397

4: 363⁴=363²⁺²=363²⋅363² ≡ 362⋅362=131044 ≡ 34 mod 397

8: 363⁸=363⁴⁺⁴=363⁴⋅363⁴ ≡ 34⋅34=1156 ≡ 362 mod 397

16: 363¹⁶=363⁸⁺⁸=363⁸⋅363⁸ ≡ 362⋅362=131044 ≡ 34 mod 397

32: 363³²=363¹⁶⁺¹⁶=363¹⁶⋅363¹⁶ ≡ 34⋅34=1156 ≡ 362 mod 397

64: 363⁶⁴=363³²⁺³²=363³²⋅363³² ≡ 362⋅362=131044 ≡ 34 mod 397

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

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

235 = 128+64+32+8+2+1

487²³⁵

= 487^{128+64+32+8+2+1}

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

≡ 64 ⋅ 611 ⋅ 576 ⋅ 569 ⋅ 92 ⋅ 487 mod 619
≡ 39104 ⋅ 576 ⋅ 569 ⋅ 92 ⋅ 487 mod 619 ≡ 107 ⋅ 576 ⋅ 569 ⋅ 92 ⋅ 487 mod 619
≡ 61632 ⋅ 569 ⋅ 92 ⋅ 487 mod 619 ≡ 351 ⋅ 569 ⋅ 92 ⋅ 487 mod 619
≡ 199719 ⋅ 92 ⋅ 487 mod 619 ≡ 401 ⋅ 92 ⋅ 487 mod 619
≡ 36892 ⋅ 487 mod 619 ≡ 371 ⋅ 487 mod 619
≡ 180677 mod 619 ≡ 548 mod 619

Es gilt also: 487²³⁵ ≡ 548 mod 619

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

=>59	= 1⋅46 + 13
=>46	= 3⋅13 + 7
=>13	= 1⋅7 + 6
=>7	= 1⋅6 + 1
=>6	= 6⋅1 + 0

also gilt: ggt(59,46)=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-1⋅6
6= 13-1⋅7	eingesetzt in die Zeile drüber:	1	= 1⋅7 -1⋅(13 -1⋅ 7) = 1⋅7 -1⋅13 +1⋅ 7) = -1⋅13 +2⋅ 7 (=1)
7= 46-3⋅13	eingesetzt in die Zeile drüber:	1	= -1⋅13 +2⋅(46 -3⋅ 13) = -1⋅13 +2⋅46 -6⋅ 13) = 2⋅46 -7⋅ 13 (=1)
13= 59-1⋅46	eingesetzt in die Zeile drüber:	1	= 2⋅46 -7⋅(59 -1⋅ 46) = 2⋅46 -7⋅59 +7⋅ 46) = -7⋅59 +9⋅ 46 (=1)

Es gilt also: ggt(59,46)=1 = -7⋅59 +9⋅46

oder wenn man -7⋅59 auf die linke Seite bringt:

1 +7⋅59 = +9⋅46

Es gilt also: 9⋅46 = 7⋅59 +1

Somit 9⋅46 = 1 mod 59

9 ist also das Inverse von 46 mod 59