Um längere Rechnungen zu vermeiden, rechnen wir:

(2395 + 1597) mod 8 ≡ (2395 mod 8 + 1597 mod 8) mod 8.

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

1597 mod 8 ≡ 5 mod 8 kann man relativ leicht bestimmen, weil ja 1597 = 1600-3 = 8 ⋅ 200 -3 = 8 ⋅ 200 - 8 + 5.

Somit gilt:

(2395 + 1597) mod 8 ≡ (3 + 5) mod 8 ≡ 8 mod 8 ≡ 0 mod 8.

Um längere Rechnungen zu vermeiden, rechnen wir:

(41 ⋅ 63) mod 4 ≡ (41 mod 4 ⋅ 63 mod 4) mod 4.

41 mod 4 ≡ 1 mod 4 kann man relativ leicht bestimmen, weil ja 41 = 40 + 1 = 10 ⋅ 4 + 1 ist.

63 mod 4 ≡ 3 mod 4 kann man relativ leicht bestimmen, weil ja 63 = 60 + 3 = 15 ⋅ 4 + 3 ist.

Somit gilt:

(41 ⋅ 63) mod 4 ≡ (1 ⋅ 3) mod 4 ≡ 3 mod 4.

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

2: 689²=689¹⁺¹=689¹⋅689¹ ≡ 689⋅689=474721 ≡ 89 mod 751

4: 689⁴=689²⁺²=689²⋅689² ≡ 89⋅89=7921 ≡ 411 mod 751

8: 689⁸=689⁴⁺⁴=689⁴⋅689⁴ ≡ 411⋅411=168921 ≡ 697 mod 751

16: 689¹⁶=689⁸⁺⁸=689⁸⋅689⁸ ≡ 697⋅697=485809 ≡ 663 mod 751

32: 689³²=689¹⁶⁺¹⁶=689¹⁶⋅689¹⁶ ≡ 663⋅663=439569 ≡ 234 mod 751

64: 689⁶⁴=689³²⁺³²=689³²⋅689³² ≡ 234⋅234=54756 ≡ 684 mod 751

128: 689¹²⁸=689⁶⁴⁺⁶⁴=689⁶⁴⋅689⁶⁴ ≡ 684⋅684=467856 ≡ 734 mod 751

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

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

91 = 64+16+8+2+1

218⁹¹

= 218^64+16+8+2+1

= 218⁶⁴⋅218¹⁶⋅218⁸⋅218²⋅218¹

≡ 91 ⋅ 98 ⋅ 154 ⋅ 47 ⋅ 218 mod 241
≡ 8918 ⋅ 154 ⋅ 47 ⋅ 218 mod 241 ≡ 1 ⋅ 154 ⋅ 47 ⋅ 218 mod 241
≡ 154 ⋅ 47 ⋅ 218 mod 241
≡ 7238 ⋅ 218 mod 241 ≡ 8 ⋅ 218 mod 241
≡ 1744 mod 241 ≡ 57 mod 241

Es gilt also: 218⁹¹ ≡ 57 mod 241

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

=>79	= 1⋅58 + 21
=>58	= 2⋅21 + 16
=>21	= 1⋅16 + 5
=>16	= 3⋅5 + 1
=>5	= 5⋅1 + 0

also gilt: ggt(79,58)=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= 16-3⋅5
5= 21-1⋅16	eingesetzt in die Zeile drüber:	1	= 1⋅16 -3⋅(21 -1⋅ 16) = 1⋅16 -3⋅21 +3⋅ 16) = -3⋅21 +4⋅ 16 (=1)
16= 58-2⋅21	eingesetzt in die Zeile drüber:	1	= -3⋅21 +4⋅(58 -2⋅ 21) = -3⋅21 +4⋅58 -8⋅ 21) = 4⋅58 -11⋅ 21 (=1)
21= 79-1⋅58	eingesetzt in die Zeile drüber:	1	= 4⋅58 -11⋅(79 -1⋅ 58) = 4⋅58 -11⋅79 +11⋅ 58) = -11⋅79 +15⋅ 58 (=1)

Es gilt also: ggt(79,58)=1 = -11⋅79 +15⋅58

oder wenn man -11⋅79 auf die linke Seite bringt:

1 +11⋅79 = +15⋅58

Es gilt also: 15⋅58 = 11⋅79 +1

Somit 15⋅58 = 1 mod 79

15 ist also das Inverse von 58 mod 79