Um längere Rechnungen zu vermeiden, rechnen wir:

(75 + 286) mod 7 ≡ (75 mod 7 + 286 mod 7) mod 7.

75 mod 7 ≡ 5 mod 7 kann man relativ leicht bestimmen, weil ja 75 = 70+5 = 7 ⋅ 10 +5.

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

Somit gilt:

(75 + 286) mod 7 ≡ (5 + 6) mod 7 ≡ 11 mod 7 ≡ 4 mod 7.

Um längere Rechnungen zu vermeiden, rechnen wir:

(24 ⋅ 82) mod 11 ≡ (24 mod 11 ⋅ 82 mod 11) mod 11.

24 mod 11 ≡ 2 mod 11 kann man relativ leicht bestimmen, weil ja 24 = 22 + 2 = 2 ⋅ 11 + 2 ist.

82 mod 11 ≡ 5 mod 11 kann man relativ leicht bestimmen, weil ja 82 = 77 + 5 = 7 ⋅ 11 + 5 ist.

Somit gilt:

(24 ⋅ 82) mod 11 ≡ (2 ⋅ 5) mod 11 ≡ 10 mod 11.

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

2: 287²=287¹⁺¹=287¹⋅287¹ ≡ 287⋅287=82369 ≡ 409 mod 683

4: 287⁴=287²⁺²=287²⋅287² ≡ 409⋅409=167281 ≡ 629 mod 683

8: 287⁸=287⁴⁺⁴=287⁴⋅287⁴ ≡ 629⋅629=395641 ≡ 184 mod 683

16: 287¹⁶=287⁸⁺⁸=287⁸⋅287⁸ ≡ 184⋅184=33856 ≡ 389 mod 683

32: 287³²=287¹⁶⁺¹⁶=287¹⁶⋅287¹⁶ ≡ 389⋅389=151321 ≡ 378 mod 683

64: 287⁶⁴=287³²⁺³²=287³²⋅287³² ≡ 378⋅378=142884 ≡ 137 mod 683

128: 287¹²⁸=287⁶⁴⁺⁶⁴=287⁶⁴⋅287⁶⁴ ≡ 137⋅137=18769 ≡ 328 mod 683

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

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

187 = 128+32+16+8+2+1

534¹⁸⁷

= 534^{128+32+16+8+2+1}

= 534¹²⁸⋅534³²⋅534¹⁶⋅534⁸⋅534²⋅534¹

≡ 384 ⋅ 142 ⋅ 36 ⋅ 6 ⋅ 118 ⋅ 534 mod 577
≡ 54528 ⋅ 36 ⋅ 6 ⋅ 118 ⋅ 534 mod 577 ≡ 290 ⋅ 36 ⋅ 6 ⋅ 118 ⋅ 534 mod 577
≡ 10440 ⋅ 6 ⋅ 118 ⋅ 534 mod 577 ≡ 54 ⋅ 6 ⋅ 118 ⋅ 534 mod 577
≡ 324 ⋅ 118 ⋅ 534 mod 577
≡ 38232 ⋅ 534 mod 577 ≡ 150 ⋅ 534 mod 577
≡ 80100 mod 577 ≡ 474 mod 577

Es gilt also: 534¹⁸⁷ ≡ 474 mod 577

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

=>89	= 1⋅71 + 18
=>71	= 3⋅18 + 17
=>18	= 1⋅17 + 1
=>17	= 17⋅1 + 0

also gilt: ggt(89,71)=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= 18-1⋅17
17= 71-3⋅18	eingesetzt in die Zeile drüber:	1	= 1⋅18 -1⋅(71 -3⋅ 18) = 1⋅18 -1⋅71 +3⋅ 18) = -1⋅71 +4⋅ 18 (=1)
18= 89-1⋅71	eingesetzt in die Zeile drüber:	1	= -1⋅71 +4⋅(89 -1⋅ 71) = -1⋅71 +4⋅89 -4⋅ 71) = 4⋅89 -5⋅ 71 (=1)

Es gilt also: ggt(89,71)=1 = 4⋅89 -5⋅71

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

1 -4⋅89 = -5⋅71

-5⋅71 = -4⋅89 + 1 |+89⋅71

-5⋅71 + 89⋅71 = -4⋅89 + 89⋅71 + 1

(-5 + 89) ⋅ 71 = (-4 + 71) ⋅ 89 + 1

84⋅71 = 67⋅89 + 1

Es gilt also: 84⋅71 = 67⋅89 +1

Somit 84⋅71 = 1 mod 89

84 ist also das Inverse von 71 mod 89