Um längere Rechnungen zu vermeiden, rechnen wir:

(6000 - 2996) mod 6 ≡ (6000 mod 6 - 2996 mod 6) mod 6.

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

2996 mod 6 ≡ 2 mod 6 kann man relativ leicht bestimmen, weil ja 2996 = 3000-4 = 6 ⋅ 500 -4 = 6 ⋅ 500 - 6 + 2.

Somit gilt:

(6000 - 2996) mod 6 ≡ (0 - 2) mod 6 ≡ -2 mod 6 ≡ 4 mod 6.

Um längere Rechnungen zu vermeiden, rechnen wir:

(84 ⋅ 53) mod 7 ≡ (84 mod 7 ⋅ 53 mod 7) mod 7.

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

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

Somit gilt:

(84 ⋅ 53) mod 7 ≡ (0 ⋅ 4) mod 7 ≡ 0 mod 7.

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

2: 597²=597¹⁺¹=597¹⋅597¹ ≡ 597⋅597=356409 ≡ 307 mod 677

4: 597⁴=597²⁺²=597²⋅597² ≡ 307⋅307=94249 ≡ 146 mod 677

8: 597⁸=597⁴⁺⁴=597⁴⋅597⁴ ≡ 146⋅146=21316 ≡ 329 mod 677

16: 597¹⁶=597⁸⁺⁸=597⁸⋅597⁸ ≡ 329⋅329=108241 ≡ 598 mod 677

32: 597³²=597¹⁶⁺¹⁶=597¹⁶⋅597¹⁶ ≡ 598⋅598=357604 ≡ 148 mod 677

64: 597⁶⁴=597³²⁺³²=597³²⋅597³² ≡ 148⋅148=21904 ≡ 240 mod 677

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

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

143 = 128+8+4+2+1

738¹⁴³

= 738^128+8+4+2+1

= 738¹²⁸⋅738⁸⋅738⁴⋅738²⋅738¹

≡ 796 ⋅ 118 ⋅ 514 ⋅ 91 ⋅ 738 mod 863
≡ 93928 ⋅ 514 ⋅ 91 ⋅ 738 mod 863 ≡ 724 ⋅ 514 ⋅ 91 ⋅ 738 mod 863
≡ 372136 ⋅ 91 ⋅ 738 mod 863 ≡ 183 ⋅ 91 ⋅ 738 mod 863
≡ 16653 ⋅ 738 mod 863 ≡ 256 ⋅ 738 mod 863
≡ 188928 mod 863 ≡ 794 mod 863

Es gilt also: 738¹⁴³ ≡ 794 mod 863

Berechnung des größten gemeinsamen Teilers von 97 und 31

=>97	= 3⋅31 + 4
=>31	= 7⋅4 + 3
=>4	= 1⋅3 + 1
=>3	= 3⋅1 + 0

also gilt: ggt(97,31)=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= 4-1⋅3
3= 31-7⋅4	eingesetzt in die Zeile drüber:	1	= 1⋅4 -1⋅(31 -7⋅ 4) = 1⋅4 -1⋅31 +7⋅ 4) = -1⋅31 +8⋅ 4 (=1)
4= 97-3⋅31	eingesetzt in die Zeile drüber:	1	= -1⋅31 +8⋅(97 -3⋅ 31) = -1⋅31 +8⋅97 -24⋅ 31) = 8⋅97 -25⋅ 31 (=1)

Es gilt also: ggt(97,31)=1 = 8⋅97 -25⋅31

oder wenn man 8⋅97 auf die linke Seite bringt:

1 -8⋅97 = -25⋅31

-25⋅31 = -8⋅97 + 1 |+97⋅31

-25⋅31 + 97⋅31 = -8⋅97 + 97⋅31 + 1

(-25 + 97) ⋅ 31 = (-8 + 31) ⋅ 97 + 1

72⋅31 = 23⋅97 + 1

Es gilt also: 72⋅31 = 23⋅97 +1

Somit 72⋅31 = 1 mod 97

72 ist also das Inverse von 31 mod 97