Um längere Rechnungen zu vermeiden, rechnen wir:

(6004 + 597) mod 6 ≡ (6004 mod 6 + 597 mod 6) mod 6.

6004 mod 6 ≡ 4 mod 6 kann man relativ leicht bestimmen, weil ja 6004 = 6000+4 = 6 ⋅ 1000 +4.

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

Somit gilt:

(6004 + 597) mod 6 ≡ (4 + 3) mod 6 ≡ 7 mod 6 ≡ 1 mod 6.

Um längere Rechnungen zu vermeiden, rechnen wir:

(83 ⋅ 92) mod 9 ≡ (83 mod 9 ⋅ 92 mod 9) mod 9.

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

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

Somit gilt:

(83 ⋅ 92) mod 9 ≡ (2 ⋅ 2) mod 9 ≡ 4 mod 9.

Die 64 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: 217¹=217

2: 217²=217¹⁺¹=217¹⋅217¹ ≡ 217⋅217=47089 ≡ 337 mod 487

4: 217⁴=217²⁺²=217²⋅217² ≡ 337⋅337=113569 ≡ 98 mod 487

8: 217⁸=217⁴⁺⁴=217⁴⋅217⁴ ≡ 98⋅98=9604 ≡ 351 mod 487

16: 217¹⁶=217⁸⁺⁸=217⁸⋅217⁸ ≡ 351⋅351=123201 ≡ 477 mod 487

32: 217³²=217¹⁶⁺¹⁶=217¹⁶⋅217¹⁶ ≡ 477⋅477=227529 ≡ 100 mod 487

64: 217⁶⁴=217³²⁺³²=217³²⋅217³² ≡ 100⋅100=10000 ≡ 260 mod 487

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

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

95 = 64+16+8+4+2+1

730⁹⁵

= 730^{64+16+8+4+2+1}

= 730⁶⁴⋅730¹⁶⋅730⁸⋅730⁴⋅730²⋅730¹

≡ 318 ⋅ 479 ⋅ 265 ⋅ 463 ⋅ 73 ⋅ 730 mod 811
≡ 152322 ⋅ 265 ⋅ 463 ⋅ 73 ⋅ 730 mod 811 ≡ 665 ⋅ 265 ⋅ 463 ⋅ 73 ⋅ 730 mod 811
≡ 176225 ⋅ 463 ⋅ 73 ⋅ 730 mod 811 ≡ 238 ⋅ 463 ⋅ 73 ⋅ 730 mod 811
≡ 110194 ⋅ 73 ⋅ 730 mod 811 ≡ 709 ⋅ 73 ⋅ 730 mod 811
≡ 51757 ⋅ 730 mod 811 ≡ 664 ⋅ 730 mod 811
≡ 484720 mod 811 ≡ 553 mod 811

Es gilt also: 730⁹⁵ ≡ 553 mod 811

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

=>89	= 2⋅41 + 7
=>41	= 5⋅7 + 6
=>7	= 1⋅6 + 1
=>6	= 6⋅1 + 0

also gilt: ggt(89,41)=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-1⋅6
6= 41-5⋅7	eingesetzt in die Zeile drüber:	1	= 1⋅7 -1⋅(41 -5⋅ 7) = 1⋅7 -1⋅41 +5⋅ 7) = -1⋅41 +6⋅ 7 (=1)
7= 89-2⋅41	eingesetzt in die Zeile drüber:	1	= -1⋅41 +6⋅(89 -2⋅ 41) = -1⋅41 +6⋅89 -12⋅ 41) = 6⋅89 -13⋅ 41 (=1)

Es gilt also: ggt(89,41)=1 = 6⋅89 -13⋅41

oder wenn man 6⋅89 auf die linke Seite bringt:

1 -6⋅89 = -13⋅41

-13⋅41 = -6⋅89 + 1 |+89⋅41

-13⋅41 + 89⋅41 = -6⋅89 + 89⋅41 + 1

(-13 + 89) ⋅ 41 = (-6 + 41) ⋅ 89 + 1

76⋅41 = 35⋅89 + 1

Es gilt also: 76⋅41 = 35⋅89 +1

Somit 76⋅41 = 1 mod 89

76 ist also das Inverse von 41 mod 89