Um längere Rechnungen zu vermeiden, rechnen wir:

(4504 - 87) mod 9 ≡ (4504 mod 9 - 87 mod 9) mod 9.

4504 mod 9 ≡ 4 mod 9 kann man relativ leicht bestimmen, weil ja 4504 = 4500+4 = 9 ⋅ 500 +4.

87 mod 9 ≡ 6 mod 9 kann man relativ leicht bestimmen, weil ja 87 = 90-3 = 9 ⋅ 10 -3 = 9 ⋅ 10 - 9 + 6.

Somit gilt:

(4504 - 87) mod 9 ≡ (4 - 6) mod 9 ≡ -2 mod 9 ≡ 7 mod 9.

Um längere Rechnungen zu vermeiden, rechnen wir:

(76 ⋅ 88) mod 5 ≡ (76 mod 5 ⋅ 88 mod 5) mod 5.

76 mod 5 ≡ 1 mod 5 kann man relativ leicht bestimmen, weil ja 76 = 75 + 1 = 15 ⋅ 5 + 1 ist.

88 mod 5 ≡ 3 mod 5 kann man relativ leicht bestimmen, weil ja 88 = 85 + 3 = 17 ⋅ 5 + 3 ist.

Somit gilt:

(76 ⋅ 88) mod 5 ≡ (1 ⋅ 3) mod 5 ≡ 3 mod 5.

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

2: 389²=389¹⁺¹=389¹⋅389¹ ≡ 389⋅389=151321 ≡ 382 mod 541

4: 389⁴=389²⁺²=389²⋅389² ≡ 382⋅382=145924 ≡ 395 mod 541

8: 389⁸=389⁴⁺⁴=389⁴⋅389⁴ ≡ 395⋅395=156025 ≡ 217 mod 541

16: 389¹⁶=389⁸⁺⁸=389⁸⋅389⁸ ≡ 217⋅217=47089 ≡ 22 mod 541

32: 389³²=389¹⁶⁺¹⁶=389¹⁶⋅389¹⁶ ≡ 22⋅22=484 ≡ 484 mod 541

64: 389⁶⁴=389³²⁺³²=389³²⋅389³² ≡ 484⋅484=234256 ≡ 3 mod 541

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

207¹⁰⁹

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

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

≡ 281 ⋅ 121 ⋅ 27 ⋅ 229 ⋅ 207 mod 359
≡ 34001 ⋅ 27 ⋅ 229 ⋅ 207 mod 359 ≡ 255 ⋅ 27 ⋅ 229 ⋅ 207 mod 359
≡ 6885 ⋅ 229 ⋅ 207 mod 359 ≡ 64 ⋅ 229 ⋅ 207 mod 359
≡ 14656 ⋅ 207 mod 359 ≡ 296 ⋅ 207 mod 359
≡ 61272 mod 359 ≡ 242 mod 359

Es gilt also: 207¹⁰⁹ ≡ 242 mod 359

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

=>89	= 1⋅51 + 38
=>51	= 1⋅38 + 13
=>38	= 2⋅13 + 12
=>13	= 1⋅12 + 1
=>12	= 12⋅1 + 0

also gilt: ggt(89,51)=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= 13-1⋅12
12= 38-2⋅13	eingesetzt in die Zeile drüber:	1	= 1⋅13 -1⋅(38 -2⋅ 13) = 1⋅13 -1⋅38 +2⋅ 13) = -1⋅38 +3⋅ 13 (=1)
13= 51-1⋅38	eingesetzt in die Zeile drüber:	1	= -1⋅38 +3⋅(51 -1⋅ 38) = -1⋅38 +3⋅51 -3⋅ 38) = 3⋅51 -4⋅ 38 (=1)
38= 89-1⋅51	eingesetzt in die Zeile drüber:	1	= 3⋅51 -4⋅(89 -1⋅ 51) = 3⋅51 -4⋅89 +4⋅ 51) = -4⋅89 +7⋅ 51 (=1)

Es gilt also: ggt(89,51)=1 = -4⋅89 +7⋅51

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

1 +4⋅89 = +7⋅51

Es gilt also: 7⋅51 = 4⋅89 +1

Somit 7⋅51 = 1 mod 89

7 ist also das Inverse von 51 mod 89