Um längere Rechnungen zu vermeiden, rechnen wir:

(1204 + 24003) mod 6 ≡ (1204 mod 6 + 24003 mod 6) mod 6.

1204 mod 6 ≡ 4 mod 6 kann man relativ leicht bestimmen, weil ja 1204 = 1200+4 = 6 ⋅ 200 +4.

24003 mod 6 ≡ 3 mod 6 kann man relativ leicht bestimmen, weil ja 24003 = 24000+3 = 6 ⋅ 4000 +3.

Somit gilt:

(1204 + 24003) mod 6 ≡ (4 + 3) mod 6 ≡ 7 mod 6 ≡ 1 mod 6.

Um längere Rechnungen zu vermeiden, rechnen wir:

(65 ⋅ 85) mod 8 ≡ (65 mod 8 ⋅ 85 mod 8) mod 8.

65 mod 8 ≡ 1 mod 8 kann man relativ leicht bestimmen, weil ja 65 = 64 + 1 = 8 ⋅ 8 + 1 ist.

85 mod 8 ≡ 5 mod 8 kann man relativ leicht bestimmen, weil ja 85 = 80 + 5 = 10 ⋅ 8 + 5 ist.

Somit gilt:

(65 ⋅ 85) mod 8 ≡ (1 ⋅ 5) mod 8 ≡ 5 mod 8.

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

2: 553²=553¹⁺¹=553¹⋅553¹ ≡ 553⋅553=305809 ≡ 148 mod 733

4: 553⁴=553²⁺²=553²⋅553² ≡ 148⋅148=21904 ≡ 647 mod 733

8: 553⁸=553⁴⁺⁴=553⁴⋅553⁴ ≡ 647⋅647=418609 ≡ 66 mod 733

16: 553¹⁶=553⁸⁺⁸=553⁸⋅553⁸ ≡ 66⋅66=4356 ≡ 691 mod 733

32: 553³²=553¹⁶⁺¹⁶=553¹⁶⋅553¹⁶ ≡ 691⋅691=477481 ≡ 298 mod 733

64: 553⁶⁴=553³²⁺³²=553³²⋅553³² ≡ 298⋅298=88804 ≡ 111 mod 733

128: 553¹²⁸=553⁶⁴⁺⁶⁴=553⁶⁴⋅553⁶⁴ ≡ 111⋅111=12321 ≡ 593 mod 733

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

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

124 = 64+32+16+8+4

152¹²⁴

= 152^64+32+16+8+4

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

≡ 70 ⋅ 178 ⋅ 412 ⋅ 436 ⋅ 90 mod 479
≡ 12460 ⋅ 412 ⋅ 436 ⋅ 90 mod 479 ≡ 6 ⋅ 412 ⋅ 436 ⋅ 90 mod 479
≡ 2472 ⋅ 436 ⋅ 90 mod 479 ≡ 77 ⋅ 436 ⋅ 90 mod 479
≡ 33572 ⋅ 90 mod 479 ≡ 42 ⋅ 90 mod 479
≡ 3780 mod 479 ≡ 427 mod 479

Es gilt also: 152¹²⁴ ≡ 427 mod 479

Berechnung des größten gemeinsamen Teilers von 83 und 77

=>83	= 1⋅77 + 6
=>77	= 12⋅6 + 5
=>6	= 1⋅5 + 1
=>5	= 5⋅1 + 0

also gilt: ggt(83,77)=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= 6-1⋅5
5= 77-12⋅6	eingesetzt in die Zeile drüber:	1	= 1⋅6 -1⋅(77 -12⋅ 6) = 1⋅6 -1⋅77 +12⋅ 6) = -1⋅77 +13⋅ 6 (=1)
6= 83-1⋅77	eingesetzt in die Zeile drüber:	1	= -1⋅77 +13⋅(83 -1⋅ 77) = -1⋅77 +13⋅83 -13⋅ 77) = 13⋅83 -14⋅ 77 (=1)

Es gilt also: ggt(83,77)=1 = 13⋅83 -14⋅77

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

1 -13⋅83 = -14⋅77

-14⋅77 = -13⋅83 + 1 |+83⋅77

-14⋅77 + 83⋅77 = -13⋅83 + 83⋅77 + 1

(-14 + 83) ⋅ 77 = (-13 + 77) ⋅ 83 + 1

69⋅77 = 64⋅83 + 1

Es gilt also: 69⋅77 = 64⋅83 +1

Somit 69⋅77 = 1 mod 83

69 ist also das Inverse von 77 mod 83