Um längere Rechnungen zu vermeiden, rechnen wir:

(4503 + 359) mod 9 ≡ (4503 mod 9 + 359 mod 9) mod 9.

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

359 mod 9 ≡ 8 mod 9 kann man relativ leicht bestimmen, weil ja 359 = 360-1 = 9 ⋅ 40 -1 = 9 ⋅ 40 - 9 + 8.

Somit gilt:

(4503 + 359) mod 9 ≡ (3 + 8) mod 9 ≡ 11 mod 9 ≡ 2 mod 9.

Um längere Rechnungen zu vermeiden, rechnen wir:

(35 ⋅ 75) mod 6 ≡ (35 mod 6 ⋅ 75 mod 6) mod 6.

35 mod 6 ≡ 5 mod 6 kann man relativ leicht bestimmen, weil ja 35 = 30 + 5 = 5 ⋅ 6 + 5 ist.

75 mod 6 ≡ 3 mod 6 kann man relativ leicht bestimmen, weil ja 75 = 72 + 3 = 12 ⋅ 6 + 3 ist.

Somit gilt:

(35 ⋅ 75) mod 6 ≡ (5 ⋅ 3) mod 6 ≡ 15 mod 6 ≡ 3 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: 230¹=230

2: 230²=230¹⁺¹=230¹⋅230¹ ≡ 230⋅230=52900 ≡ 385 mod 389

4: 230⁴=230²⁺²=230²⋅230² ≡ 385⋅385=148225 ≡ 16 mod 389

8: 230⁸=230⁴⁺⁴=230⁴⋅230⁴ ≡ 16⋅16=256 ≡ 256 mod 389

16: 230¹⁶=230⁸⁺⁸=230⁸⋅230⁸ ≡ 256⋅256=65536 ≡ 184 mod 389

32: 230³²=230¹⁶⁺¹⁶=230¹⁶⋅230¹⁶ ≡ 184⋅184=33856 ≡ 13 mod 389

64: 230⁶⁴=230³²⁺³²=230³²⋅230³² ≡ 13⋅13=169 ≡ 169 mod 389

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

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

188 = 128+32+16+8+4

333¹⁸⁸

= 333^{128+32+16+8+4}

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

≡ 213 ⋅ 364 ⋅ 520 ⋅ 382 ⋅ 62 mod 577
≡ 77532 ⋅ 520 ⋅ 382 ⋅ 62 mod 577 ≡ 214 ⋅ 520 ⋅ 382 ⋅ 62 mod 577
≡ 111280 ⋅ 382 ⋅ 62 mod 577 ≡ 496 ⋅ 382 ⋅ 62 mod 577
≡ 189472 ⋅ 62 mod 577 ≡ 216 ⋅ 62 mod 577
≡ 13392 mod 577 ≡ 121 mod 577

Es gilt also: 333¹⁸⁸ ≡ 121 mod 577

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

=>71	= 1⋅42 + 29
=>42	= 1⋅29 + 13
=>29	= 2⋅13 + 3
=>13	= 4⋅3 + 1
=>3	= 3⋅1 + 0

also gilt: ggt(71,42)=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-4⋅3
3= 29-2⋅13	eingesetzt in die Zeile drüber:	1	= 1⋅13 -4⋅(29 -2⋅ 13) = 1⋅13 -4⋅29 +8⋅ 13) = -4⋅29 +9⋅ 13 (=1)
13= 42-1⋅29	eingesetzt in die Zeile drüber:	1	= -4⋅29 +9⋅(42 -1⋅ 29) = -4⋅29 +9⋅42 -9⋅ 29) = 9⋅42 -13⋅ 29 (=1)
29= 71-1⋅42	eingesetzt in die Zeile drüber:	1	= 9⋅42 -13⋅(71 -1⋅ 42) = 9⋅42 -13⋅71 +13⋅ 42) = -13⋅71 +22⋅ 42 (=1)

Es gilt also: ggt(71,42)=1 = -13⋅71 +22⋅42

oder wenn man -13⋅71 auf die linke Seite bringt:

1 +13⋅71 = +22⋅42

Es gilt also: 22⋅42 = 13⋅71 +1

Somit 22⋅42 = 1 mod 71

22 ist also das Inverse von 42 mod 71