Um längere Rechnungen zu vermeiden, rechnen wir:

(594 - 2395) mod 6 ≡ (594 mod 6 - 2395 mod 6) mod 6.

594 mod 6 ≡ 0 mod 6 kann man relativ leicht bestimmen, weil ja 594 = 600-6 = 6 ⋅ 100 -6 = 6 ⋅ 100 - 6 + 0.

2395 mod 6 ≡ 1 mod 6 kann man relativ leicht bestimmen, weil ja 2395 = 2400-5 = 6 ⋅ 400 -5 = 6 ⋅ 400 - 6 + 1.

Somit gilt:

(594 - 2395) mod 6 ≡ (0 - 1) mod 6 ≡ -1 mod 6 ≡ 5 mod 6.

Um längere Rechnungen zu vermeiden, rechnen wir:

(96 ⋅ 17) mod 7 ≡ (96 mod 7 ⋅ 17 mod 7) mod 7.

96 mod 7 ≡ 5 mod 7 kann man relativ leicht bestimmen, weil ja 96 = 91 + 5 = 13 ⋅ 7 + 5 ist.

17 mod 7 ≡ 3 mod 7 kann man relativ leicht bestimmen, weil ja 17 = 14 + 3 = 2 ⋅ 7 + 3 ist.

Somit gilt:

(96 ⋅ 17) mod 7 ≡ (5 ⋅ 3) mod 7 ≡ 15 mod 7 ≡ 1 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: 225¹=225

2: 225²=225¹⁺¹=225¹⋅225¹ ≡ 225⋅225=50625 ≡ 251 mod 283

4: 225⁴=225²⁺²=225²⋅225² ≡ 251⋅251=63001 ≡ 175 mod 283

8: 225⁸=225⁴⁺⁴=225⁴⋅225⁴ ≡ 175⋅175=30625 ≡ 61 mod 283

16: 225¹⁶=225⁸⁺⁸=225⁸⋅225⁸ ≡ 61⋅61=3721 ≡ 42 mod 283

32: 225³²=225¹⁶⁺¹⁶=225¹⁶⋅225¹⁶ ≡ 42⋅42=1764 ≡ 66 mod 283

64: 225⁶⁴=225³²⁺³²=225³²⋅225³² ≡ 66⋅66=4356 ≡ 111 mod 283

128: 225¹²⁸=225⁶⁴⁺⁶⁴=225⁶⁴⋅225⁶⁴ ≡ 111⋅111=12321 ≡ 152 mod 283

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

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

122 = 64+32+16+8+2

387¹²²

= 387^64+32+16+8+2

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

≡ 107 ⋅ 374 ⋅ 53 ⋅ 370 ⋅ 260 mod 487
≡ 40018 ⋅ 53 ⋅ 370 ⋅ 260 mod 487 ≡ 84 ⋅ 53 ⋅ 370 ⋅ 260 mod 487
≡ 4452 ⋅ 370 ⋅ 260 mod 487 ≡ 69 ⋅ 370 ⋅ 260 mod 487
≡ 25530 ⋅ 260 mod 487 ≡ 206 ⋅ 260 mod 487
≡ 53560 mod 487 ≡ 477 mod 487

Es gilt also: 387¹²² ≡ 477 mod 487

Berechnung des größten gemeinsamen Teilers von 79 und 24

=>79	= 3⋅24 + 7
=>24	= 3⋅7 + 3
=>7	= 2⋅3 + 1
=>3	= 3⋅1 + 0

also gilt: ggt(79,24)=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= 7-2⋅3
3= 24-3⋅7	eingesetzt in die Zeile drüber:	1	= 1⋅7 -2⋅(24 -3⋅ 7) = 1⋅7 -2⋅24 +6⋅ 7) = -2⋅24 +7⋅ 7 (=1)
7= 79-3⋅24	eingesetzt in die Zeile drüber:	1	= -2⋅24 +7⋅(79 -3⋅ 24) = -2⋅24 +7⋅79 -21⋅ 24) = 7⋅79 -23⋅ 24 (=1)

Es gilt also: ggt(79,24)=1 = 7⋅79 -23⋅24

oder wenn man 7⋅79 auf die linke Seite bringt:

1 -7⋅79 = -23⋅24

-23⋅24 = -7⋅79 + 1 |+79⋅24

-23⋅24 + 79⋅24 = -7⋅79 + 79⋅24 + 1

(-23 + 79) ⋅ 24 = (-7 + 24) ⋅ 79 + 1

56⋅24 = 17⋅79 + 1

Es gilt also: 56⋅24 = 17⋅79 +1

Somit 56⋅24 = 1 mod 79

56 ist also das Inverse von 24 mod 79