Um längere Rechnungen zu vermeiden, rechnen wir:

(3507 - 285) mod 7 ≡ (3507 mod 7 - 285 mod 7) mod 7.

3507 mod 7 ≡ 0 mod 7 kann man relativ leicht bestimmen, weil ja 3507 = 3500+7 = 7 ⋅ 500 +7.

285 mod 7 ≡ 5 mod 7 kann man relativ leicht bestimmen, weil ja 285 = 280+5 = 7 ⋅ 40 +5.

Somit gilt:

(3507 - 285) mod 7 ≡ (0 - 5) mod 7 ≡ -5 mod 7 ≡ 2 mod 7.

Um längere Rechnungen zu vermeiden, rechnen wir:

(79 ⋅ 60) mod 10 ≡ (79 mod 10 ⋅ 60 mod 10) mod 10.

79 mod 10 ≡ 9 mod 10 kann man relativ leicht bestimmen, weil ja 79 = 70 + 9 = 7 ⋅ 10 + 9 ist.

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

Somit gilt:

(79 ⋅ 60) mod 10 ≡ (9 ⋅ 0) mod 10 ≡ 0 mod 10.

Die 128 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: 279¹=279

2: 279²=279¹⁺¹=279¹⋅279¹ ≡ 279⋅279=77841 ≡ 796 mod 811

4: 279⁴=279²⁺²=279²⋅279² ≡ 796⋅796=633616 ≡ 225 mod 811

8: 279⁸=279⁴⁺⁴=279⁴⋅279⁴ ≡ 225⋅225=50625 ≡ 343 mod 811

16: 279¹⁶=279⁸⁺⁸=279⁸⋅279⁸ ≡ 343⋅343=117649 ≡ 54 mod 811

32: 279³²=279¹⁶⁺¹⁶=279¹⁶⋅279¹⁶ ≡ 54⋅54=2916 ≡ 483 mod 811

64: 279⁶⁴=279³²⁺³²=279³²⋅279³² ≡ 483⋅483=233289 ≡ 532 mod 811

128: 279¹²⁸=279⁶⁴⁺⁶⁴=279⁶⁴⋅279⁶⁴ ≡ 532⋅532=283024 ≡ 796 mod 811

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

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

79 = 64+8+4+2+1

205⁷⁹

= 205^64+8+4+2+1

= 205⁶⁴⋅205⁸⋅205⁴⋅205²⋅205¹

≡ 80 ⋅ 370 ⋅ 405 ⋅ 74 ⋅ 205 mod 461
≡ 29600 ⋅ 405 ⋅ 74 ⋅ 205 mod 461 ≡ 96 ⋅ 405 ⋅ 74 ⋅ 205 mod 461
≡ 38880 ⋅ 74 ⋅ 205 mod 461 ≡ 156 ⋅ 74 ⋅ 205 mod 461
≡ 11544 ⋅ 205 mod 461 ≡ 19 ⋅ 205 mod 461
≡ 3895 mod 461 ≡ 207 mod 461

Es gilt also: 205⁷⁹ ≡ 207 mod 461

Berechnung des größten gemeinsamen Teilers von 89 und 77

=>89	= 1⋅77 + 12
=>77	= 6⋅12 + 5
=>12	= 2⋅5 + 2
=>5	= 2⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(89,77)=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= 5-2⋅2
2= 12-2⋅5	eingesetzt in die Zeile drüber:	1	= 1⋅5 -2⋅(12 -2⋅ 5) = 1⋅5 -2⋅12 +4⋅ 5) = -2⋅12 +5⋅ 5 (=1)
5= 77-6⋅12	eingesetzt in die Zeile drüber:	1	= -2⋅12 +5⋅(77 -6⋅ 12) = -2⋅12 +5⋅77 -30⋅ 12) = 5⋅77 -32⋅ 12 (=1)
12= 89-1⋅77	eingesetzt in die Zeile drüber:	1	= 5⋅77 -32⋅(89 -1⋅ 77) = 5⋅77 -32⋅89 +32⋅ 77) = -32⋅89 +37⋅ 77 (=1)

Es gilt also: ggt(89,77)=1 = -32⋅89 +37⋅77

oder wenn man -32⋅89 auf die linke Seite bringt:

1 +32⋅89 = +37⋅77

Es gilt also: 37⋅77 = 32⋅89 +1

Somit 37⋅77 = 1 mod 89

37 ist also das Inverse von 77 mod 89