Um längere Rechnungen zu vermeiden, rechnen wir:

(3599 + 26997) mod 9 ≡ (3599 mod 9 + 26997 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.

26997 mod 9 ≡ 6 mod 9 kann man relativ leicht bestimmen, weil ja 26997 = 27000-3 = 9 ⋅ 3000 -3 = 9 ⋅ 3000 - 9 + 6.

Somit gilt:

(3599 + 26997) mod 9 ≡ (8 + 6) mod 9 ≡ 14 mod 9 ≡ 5 mod 9.

Um längere Rechnungen zu vermeiden, rechnen wir:

(93 ⋅ 75) mod 11 ≡ (93 mod 11 ⋅ 75 mod 11) mod 11.

93 mod 11 ≡ 5 mod 11 kann man relativ leicht bestimmen, weil ja 93 = 88 + 5 = 8 ⋅ 11 + 5 ist.

75 mod 11 ≡ 9 mod 11 kann man relativ leicht bestimmen, weil ja 75 = 66 + 9 = 6 ⋅ 11 + 9 ist.

Somit gilt:

(93 ⋅ 75) mod 11 ≡ (5 ⋅ 9) mod 11 ≡ 45 mod 11 ≡ 1 mod 11.

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

2: 415²=415¹⁺¹=415¹⋅415¹ ≡ 415⋅415=172225 ≡ 467 mod 547

4: 415⁴=415²⁺²=415²⋅415² ≡ 467⋅467=218089 ≡ 383 mod 547

8: 415⁸=415⁴⁺⁴=415⁴⋅415⁴ ≡ 383⋅383=146689 ≡ 93 mod 547

16: 415¹⁶=415⁸⁺⁸=415⁸⋅415⁸ ≡ 93⋅93=8649 ≡ 444 mod 547

32: 415³²=415¹⁶⁺¹⁶=415¹⁶⋅415¹⁶ ≡ 444⋅444=197136 ≡ 216 mod 547

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

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

181 = 128+32+16+4+1

340¹⁸¹

= 340^{128+32+16+4+1}

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

≡ 231 ⋅ 550 ⋅ 833 ⋅ 200 ⋅ 340 mod 967
≡ 127050 ⋅ 833 ⋅ 200 ⋅ 340 mod 967 ≡ 373 ⋅ 833 ⋅ 200 ⋅ 340 mod 967
≡ 310709 ⋅ 200 ⋅ 340 mod 967 ≡ 302 ⋅ 200 ⋅ 340 mod 967
≡ 60400 ⋅ 340 mod 967 ≡ 446 ⋅ 340 mod 967
≡ 151640 mod 967 ≡ 788 mod 967

Es gilt also: 340¹⁸¹ ≡ 788 mod 967

Berechnung des größten gemeinsamen Teilers von 53 und 43

=>53	= 1⋅43 + 10
=>43	= 4⋅10 + 3
=>10	= 3⋅3 + 1
=>3	= 3⋅1 + 0

also gilt: ggt(53,43)=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= 10-3⋅3
3= 43-4⋅10	eingesetzt in die Zeile drüber:	1	= 1⋅10 -3⋅(43 -4⋅ 10) = 1⋅10 -3⋅43 +12⋅ 10) = -3⋅43 +13⋅ 10 (=1)
10= 53-1⋅43	eingesetzt in die Zeile drüber:	1	= -3⋅43 +13⋅(53 -1⋅ 43) = -3⋅43 +13⋅53 -13⋅ 43) = 13⋅53 -16⋅ 43 (=1)

Es gilt also: ggt(53,43)=1 = 13⋅53 -16⋅43

oder wenn man 13⋅53 auf die linke Seite bringt:

1 -13⋅53 = -16⋅43

-16⋅43 = -13⋅53 + 1 |+53⋅43

-16⋅43 + 53⋅43 = -13⋅53 + 53⋅43 + 1

(-16 + 53) ⋅ 43 = (-13 + 43) ⋅ 53 + 1

37⋅43 = 30⋅53 + 1

Es gilt also: 37⋅43 = 30⋅53 +1

Somit 37⋅43 = 1 mod 53

37 ist also das Inverse von 43 mod 53