Um längere Rechnungen zu vermeiden, rechnen wir:

(3599 + 2693) mod 9 ≡ (3599 mod 9 + 2693 mod 9) mod 9.

3599 mod 9 ≡ 8 mod 9 kann man relativ leicht bestimmen, weil ja 3599 = 3600-1 = 9 ⋅ 400 -1 = 9 ⋅ 400 - 9 + 8.

2693 mod 9 ≡ 2 mod 9 kann man relativ leicht bestimmen, weil ja 2693 = 2700-7 = 9 ⋅ 300 -7 = 9 ⋅ 300 - 9 + 2.

Somit gilt:

(3599 + 2693) mod 9 ≡ (8 + 2) mod 9 ≡ 10 mod 9 ≡ 1 mod 9.

Um längere Rechnungen zu vermeiden, rechnen wir:

(24 ⋅ 90) mod 10 ≡ (24 mod 10 ⋅ 90 mod 10) mod 10.

24 mod 10 ≡ 4 mod 10 kann man relativ leicht bestimmen, weil ja 24 = 20 + 4 = 2 ⋅ 10 + 4 ist.

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

Somit gilt:

(24 ⋅ 90) mod 10 ≡ (4 ⋅ 0) mod 10 ≡ 0 mod 10.

Die 32 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: 497¹=497

2: 497²=497¹⁺¹=497¹⋅497¹ ≡ 497⋅497=247009 ≡ 144 mod 509

4: 497⁴=497²⁺²=497²⋅497² ≡ 144⋅144=20736 ≡ 376 mod 509

8: 497⁸=497⁴⁺⁴=497⁴⋅497⁴ ≡ 376⋅376=141376 ≡ 383 mod 509

16: 497¹⁶=497⁸⁺⁸=497⁸⋅497⁸ ≡ 383⋅383=146689 ≡ 97 mod 509

32: 497³²=497¹⁶⁺¹⁶=497¹⁶⋅497¹⁶ ≡ 97⋅97=9409 ≡ 247 mod 509

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

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

87 = 64+16+4+2+1

175⁸⁷

= 175^64+16+4+2+1

= 175⁶⁴⋅175¹⁶⋅175⁴⋅175²⋅175¹

≡ 147 ⋅ 118 ⋅ 41 ⋅ 329 ⋅ 175 mod 541
≡ 17346 ⋅ 41 ⋅ 329 ⋅ 175 mod 541 ≡ 34 ⋅ 41 ⋅ 329 ⋅ 175 mod 541
≡ 1394 ⋅ 329 ⋅ 175 mod 541 ≡ 312 ⋅ 329 ⋅ 175 mod 541
≡ 102648 ⋅ 175 mod 541 ≡ 399 ⋅ 175 mod 541
≡ 69825 mod 541 ≡ 36 mod 541

Es gilt also: 175⁸⁷ ≡ 36 mod 541

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