Um längere Rechnungen zu vermeiden, rechnen wir:

(5994 - 596) mod 6 ≡ (5994 mod 6 - 596 mod 6) mod 6.

5994 mod 6 ≡ 0 mod 6 kann man relativ leicht bestimmen, weil ja 5994 = 6000-6 = 6 ⋅ 1000 -6 = 6 ⋅ 1000 - 6 + 0.

596 mod 6 ≡ 2 mod 6 kann man relativ leicht bestimmen, weil ja 596 = 600-4 = 6 ⋅ 100 -4 = 6 ⋅ 100 - 6 + 2.

Somit gilt:

(5994 - 596) mod 6 ≡ (0 - 2) mod 6 ≡ -2 mod 6 ≡ 4 mod 6.

Um längere Rechnungen zu vermeiden, rechnen wir:

(97 ⋅ 86) mod 9 ≡ (97 mod 9 ⋅ 86 mod 9) mod 9.

97 mod 9 ≡ 7 mod 9 kann man relativ leicht bestimmen, weil ja 97 = 90 + 7 = 10 ⋅ 9 + 7 ist.

86 mod 9 ≡ 5 mod 9 kann man relativ leicht bestimmen, weil ja 86 = 81 + 5 = 9 ⋅ 9 + 5 ist.

Somit gilt:

(97 ⋅ 86) mod 9 ≡ (7 ⋅ 5) mod 9 ≡ 35 mod 9 ≡ 8 mod 9.

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

2: 669²=669¹⁺¹=669¹⋅669¹ ≡ 669⋅669=447561 ≡ 260 mod 911

4: 669⁴=669²⁺²=669²⋅669² ≡ 260⋅260=67600 ≡ 186 mod 911

8: 669⁸=669⁴⁺⁴=669⁴⋅669⁴ ≡ 186⋅186=34596 ≡ 889 mod 911

16: 669¹⁶=669⁸⁺⁸=669⁸⋅669⁸ ≡ 889⋅889=790321 ≡ 484 mod 911

32: 669³²=669¹⁶⁺¹⁶=669¹⁶⋅669¹⁶ ≡ 484⋅484=234256 ≡ 129 mod 911

64: 669⁶⁴=669³²⁺³²=669³²⋅669³² ≡ 129⋅129=16641 ≡ 243 mod 911

128: 669¹²⁸=669⁶⁴⁺⁶⁴=669⁶⁴⋅669⁶⁴ ≡ 243⋅243=59049 ≡ 745 mod 911

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

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

161 = 128+32+1

296¹⁶¹

= 296^128+32+1

= 296¹²⁸⋅296³²⋅296¹

≡ 374 ⋅ 19 ⋅ 296 mod 653
≡ 7106 ⋅ 296 mod 653 ≡ 576 ⋅ 296 mod 653
≡ 170496 mod 653 ≡ 63 mod 653

Es gilt also: 296¹⁶¹ ≡ 63 mod 653

Berechnung des größten gemeinsamen Teilers von 53 und 28

=>53	= 1⋅28 + 25
=>28	= 1⋅25 + 3
=>25	= 8⋅3 + 1
=>3	= 3⋅1 + 0

also gilt: ggt(53,28)=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= 25-8⋅3
3= 28-1⋅25	eingesetzt in die Zeile drüber:	1	= 1⋅25 -8⋅(28 -1⋅ 25) = 1⋅25 -8⋅28 +8⋅ 25) = -8⋅28 +9⋅ 25 (=1)
25= 53-1⋅28	eingesetzt in die Zeile drüber:	1	= -8⋅28 +9⋅(53 -1⋅ 28) = -8⋅28 +9⋅53 -9⋅ 28) = 9⋅53 -17⋅ 28 (=1)

Es gilt also: ggt(53,28)=1 = 9⋅53 -17⋅28

oder wenn man 9⋅53 auf die linke Seite bringt:

1 -9⋅53 = -17⋅28

-17⋅28 = -9⋅53 + 1 |+53⋅28

-17⋅28 + 53⋅28 = -9⋅53 + 53⋅28 + 1

(-17 + 53) ⋅ 28 = (-9 + 28) ⋅ 53 + 1

36⋅28 = 19⋅53 + 1

Es gilt also: 36⋅28 = 19⋅53 +1

Somit 36⋅28 = 1 mod 53

36 ist also das Inverse von 28 mod 53