Um längere Rechnungen zu vermeiden, rechnen wir:

(24004 + 24006) mod 8 ≡ (24004 mod 8 + 24006 mod 8) mod 8.

24004 mod 8 ≡ 4 mod 8 kann man relativ leicht bestimmen, weil ja 24004 = 24000+4 = 8 ⋅ 3000 +4.

24006 mod 8 ≡ 6 mod 8 kann man relativ leicht bestimmen, weil ja 24006 = 24000+6 = 8 ⋅ 3000 +6.

Somit gilt:

(24004 + 24006) mod 8 ≡ (4 + 6) mod 8 ≡ 10 mod 8 ≡ 2 mod 8.

Um längere Rechnungen zu vermeiden, rechnen wir:

(15 ⋅ 54) mod 5 ≡ (15 mod 5 ⋅ 54 mod 5) mod 5.

15 mod 5 ≡ 0 mod 5 kann man relativ leicht bestimmen, weil ja 15 = 15 + 0 = 3 ⋅ 5 + 0 ist.

54 mod 5 ≡ 4 mod 5 kann man relativ leicht bestimmen, weil ja 54 = 50 + 4 = 10 ⋅ 5 + 4 ist.

Somit gilt:

(15 ⋅ 54) mod 5 ≡ (0 ⋅ 4) mod 5 ≡ 0 mod 5.

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

2: 358²=358¹⁺¹=358¹⋅358¹ ≡ 358⋅358=128164 ≡ 70 mod 577

4: 358⁴=358²⁺²=358²⋅358² ≡ 70⋅70=4900 ≡ 284 mod 577

8: 358⁸=358⁴⁺⁴=358⁴⋅358⁴ ≡ 284⋅284=80656 ≡ 453 mod 577

16: 358¹⁶=358⁸⁺⁸=358⁸⋅358⁸ ≡ 453⋅453=205209 ≡ 374 mod 577

32: 358³²=358¹⁶⁺¹⁶=358¹⁶⋅358¹⁶ ≡ 374⋅374=139876 ≡ 242 mod 577

64: 358⁶⁴=358³²⁺³²=358³²⋅358³² ≡ 242⋅242=58564 ≡ 287 mod 577

128: 358¹²⁸=358⁶⁴⁺⁶⁴=358⁶⁴⋅358⁶⁴ ≡ 287⋅287=82369 ≡ 435 mod 577

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

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

212 = 128+64+16+4

679²¹²

= 679^128+64+16+4

= 679¹²⁸⋅679⁶⁴⋅679¹⁶⋅679⁴

≡ 674 ⋅ 565 ⋅ 605 ⋅ 6 mod 691
≡ 380810 ⋅ 605 ⋅ 6 mod 691 ≡ 69 ⋅ 605 ⋅ 6 mod 691
≡ 41745 ⋅ 6 mod 691 ≡ 285 ⋅ 6 mod 691
≡ 1710 mod 691 ≡ 328 mod 691

Es gilt also: 679²¹² ≡ 328 mod 691

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

=>83	= 1⋅55 + 28
=>55	= 1⋅28 + 27
=>28	= 1⋅27 + 1
=>27	= 27⋅1 + 0

also gilt: ggt(83,55)=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= 28-1⋅27
27= 55-1⋅28	eingesetzt in die Zeile drüber:	1	= 1⋅28 -1⋅(55 -1⋅ 28) = 1⋅28 -1⋅55 +1⋅ 28) = -1⋅55 +2⋅ 28 (=1)
28= 83-1⋅55	eingesetzt in die Zeile drüber:	1	= -1⋅55 +2⋅(83 -1⋅ 55) = -1⋅55 +2⋅83 -2⋅ 55) = 2⋅83 -3⋅ 55 (=1)

Es gilt also: ggt(83,55)=1 = 2⋅83 -3⋅55

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

1 -2⋅83 = -3⋅55

-3⋅55 = -2⋅83 + 1 |+83⋅55

-3⋅55 + 83⋅55 = -2⋅83 + 83⋅55 + 1

(-3 + 83) ⋅ 55 = (-2 + 55) ⋅ 83 + 1

80⋅55 = 53⋅83 + 1

Es gilt also: 80⋅55 = 53⋅83 +1

Somit 80⋅55 = 1 mod 83

80 ist also das Inverse von 55 mod 83