Um längere Rechnungen zu vermeiden, rechnen wir:

(98 - 3605) mod 9 ≡ (98 mod 9 - 3605 mod 9) mod 9.

98 mod 9 ≡ 8 mod 9 kann man relativ leicht bestimmen, weil ja 98 = 90+8 = 9 ⋅ 10 +8.

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

Somit gilt:

(98 - 3605) mod 9 ≡ (8 - 5) mod 9 ≡ 3 mod 9.

Um längere Rechnungen zu vermeiden, rechnen wir:

(64 ⋅ 18) mod 6 ≡ (64 mod 6 ⋅ 18 mod 6) mod 6.

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

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

Somit gilt:

(64 ⋅ 18) mod 6 ≡ (4 ⋅ 0) mod 6 ≡ 0 mod 6.

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

2: 394²=394¹⁺¹=394¹⋅394¹ ≡ 394⋅394=155236 ≡ 847 mod 971

4: 394⁴=394²⁺²=394²⋅394² ≡ 847⋅847=717409 ≡ 811 mod 971

8: 394⁸=394⁴⁺⁴=394⁴⋅394⁴ ≡ 811⋅811=657721 ≡ 354 mod 971

16: 394¹⁶=394⁸⁺⁸=394⁸⋅394⁸ ≡ 354⋅354=125316 ≡ 57 mod 971

32: 394³²=394¹⁶⁺¹⁶=394¹⁶⋅394¹⁶ ≡ 57⋅57=3249 ≡ 336 mod 971

64: 394⁶⁴=394³²⁺³²=394³²⋅394³² ≡ 336⋅336=112896 ≡ 260 mod 971

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

543¹⁰⁹

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

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

≡ 795 ⋅ 351 ⋅ 467 ⋅ 175 ⋅ 543 mod 887
≡ 279045 ⋅ 467 ⋅ 175 ⋅ 543 mod 887 ≡ 527 ⋅ 467 ⋅ 175 ⋅ 543 mod 887
≡ 246109 ⋅ 175 ⋅ 543 mod 887 ≡ 410 ⋅ 175 ⋅ 543 mod 887
≡ 71750 ⋅ 543 mod 887 ≡ 790 ⋅ 543 mod 887
≡ 428970 mod 887 ≡ 549 mod 887

Es gilt also: 543¹⁰⁹ ≡ 549 mod 887

Berechnung des größten gemeinsamen Teilers von 101 und 35

=>101	= 2⋅35 + 31
=>35	= 1⋅31 + 4
=>31	= 7⋅4 + 3
=>4	= 1⋅3 + 1
=>3	= 3⋅1 + 0

also gilt: ggt(101,35)=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= 4-1⋅3
3= 31-7⋅4	eingesetzt in die Zeile drüber:	1	= 1⋅4 -1⋅(31 -7⋅ 4) = 1⋅4 -1⋅31 +7⋅ 4) = -1⋅31 +8⋅ 4 (=1)
4= 35-1⋅31	eingesetzt in die Zeile drüber:	1	= -1⋅31 +8⋅(35 -1⋅ 31) = -1⋅31 +8⋅35 -8⋅ 31) = 8⋅35 -9⋅ 31 (=1)
31= 101-2⋅35	eingesetzt in die Zeile drüber:	1	= 8⋅35 -9⋅(101 -2⋅ 35) = 8⋅35 -9⋅101 +18⋅ 35) = -9⋅101 +26⋅ 35 (=1)

Es gilt also: ggt(101,35)=1 = -9⋅101 +26⋅35

oder wenn man -9⋅101 auf die linke Seite bringt:

1 +9⋅101 = +26⋅35

Es gilt also: 26⋅35 = 9⋅101 +1

Somit 26⋅35 = 1 mod 101

26 ist also das Inverse von 35 mod 101