Um längere Rechnungen zu vermeiden, rechnen wir:

(2397 + 164) mod 8 ≡ (2397 mod 8 + 164 mod 8) mod 8.

2397 mod 8 ≡ 5 mod 8 kann man relativ leicht bestimmen, weil ja 2397 = 2400-3 = 8 ⋅ 300 -3 = 8 ⋅ 300 - 8 + 5.

164 mod 8 ≡ 4 mod 8 kann man relativ leicht bestimmen, weil ja 164 = 160+4 = 8 ⋅ 20 +4.

Somit gilt:

(2397 + 164) mod 8 ≡ (5 + 4) mod 8 ≡ 9 mod 8 ≡ 1 mod 8.

Um längere Rechnungen zu vermeiden, rechnen wir:

(32 ⋅ 49) mod 7 ≡ (32 mod 7 ⋅ 49 mod 7) mod 7.

32 mod 7 ≡ 4 mod 7 kann man relativ leicht bestimmen, weil ja 32 = 28 + 4 = 4 ⋅ 7 + 4 ist.

49 mod 7 ≡ 0 mod 7 kann man relativ leicht bestimmen, weil ja 49 = 49 + 0 = 7 ⋅ 7 + 0 ist.

Somit gilt:

(32 ⋅ 49) mod 7 ≡ (4 ⋅ 0) mod 7 ≡ 0 mod 7.

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

2: 269²=269¹⁺¹=269¹⋅269¹ ≡ 269⋅269=72361 ≡ 83 mod 509

4: 269⁴=269²⁺²=269²⋅269² ≡ 83⋅83=6889 ≡ 272 mod 509

8: 269⁸=269⁴⁺⁴=269⁴⋅269⁴ ≡ 272⋅272=73984 ≡ 179 mod 509

16: 269¹⁶=269⁸⁺⁸=269⁸⋅269⁸ ≡ 179⋅179=32041 ≡ 483 mod 509

32: 269³²=269¹⁶⁺¹⁶=269¹⁶⋅269¹⁶ ≡ 483⋅483=233289 ≡ 167 mod 509

64: 269⁶⁴=269³²⁺³²=269³²⋅269³² ≡ 167⋅167=27889 ≡ 403 mod 509

128: 269¹²⁸=269⁶⁴⁺⁶⁴=269⁶⁴⋅269⁶⁴ ≡ 403⋅403=162409 ≡ 38 mod 509

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

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

118 = 64+32+16+4+2

413¹¹⁸

= 413^64+32+16+4+2

= 413⁶⁴⋅413³²⋅413¹⁶⋅413⁴⋅413²

≡ 144 ⋅ 12 ⋅ 588 ⋅ 118 ⋅ 155 mod 613
≡ 1728 ⋅ 588 ⋅ 118 ⋅ 155 mod 613 ≡ 502 ⋅ 588 ⋅ 118 ⋅ 155 mod 613
≡ 295176 ⋅ 118 ⋅ 155 mod 613 ≡ 323 ⋅ 118 ⋅ 155 mod 613
≡ 38114 ⋅ 155 mod 613 ≡ 108 ⋅ 155 mod 613
≡ 16740 mod 613 ≡ 189 mod 613

Es gilt also: 413¹¹⁸ ≡ 189 mod 613

Berechnung des größten gemeinsamen Teilers von 89 und 82

=>89	= 1⋅82 + 7
=>82	= 11⋅7 + 5
=>7	= 1⋅5 + 2
=>5	= 2⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(89,82)=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= 5-2⋅2
2= 7-1⋅5	eingesetzt in die Zeile drüber:	1	= 1⋅5 -2⋅(7 -1⋅ 5) = 1⋅5 -2⋅7 +2⋅ 5) = -2⋅7 +3⋅ 5 (=1)
5= 82-11⋅7	eingesetzt in die Zeile drüber:	1	= -2⋅7 +3⋅(82 -11⋅ 7) = -2⋅7 +3⋅82 -33⋅ 7) = 3⋅82 -35⋅ 7 (=1)
7= 89-1⋅82	eingesetzt in die Zeile drüber:	1	= 3⋅82 -35⋅(89 -1⋅ 82) = 3⋅82 -35⋅89 +35⋅ 82) = -35⋅89 +38⋅ 82 (=1)

Es gilt also: ggt(89,82)=1 = -35⋅89 +38⋅82

oder wenn man -35⋅89 auf die linke Seite bringt:

1 +35⋅89 = +38⋅82

Es gilt also: 38⋅82 = 35⋅89 +1

Somit 38⋅82 = 1 mod 89

38 ist also das Inverse von 82 mod 89