Um längere Rechnungen zu vermeiden, rechnen wir:

(13997 - 702) mod 7 ≡ (13997 mod 7 - 702 mod 7) mod 7.

13997 mod 7 ≡ 4 mod 7 kann man relativ leicht bestimmen, weil ja 13997 = 14000-3 = 7 ⋅ 2000 -3 = 7 ⋅ 2000 - 7 + 4.

702 mod 7 ≡ 2 mod 7 kann man relativ leicht bestimmen, weil ja 702 = 700+2 = 7 ⋅ 100 +2.

Somit gilt:

(13997 - 702) mod 7 ≡ (4 - 2) mod 7 ≡ 2 mod 7.

Um längere Rechnungen zu vermeiden, rechnen wir:

(92 ⋅ 94) mod 3 ≡ (92 mod 3 ⋅ 94 mod 3) mod 3.

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

94 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 94 = 93 + 1 = 31 ⋅ 3 + 1 ist.

Somit gilt:

(92 ⋅ 94) mod 3 ≡ (2 ⋅ 1) mod 3 ≡ 2 mod 3.

Die 32 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: 449¹=449

2: 449²=449¹⁺¹=449¹⋅449¹ ≡ 449⋅449=201601 ≡ 640 mod 827

4: 449⁴=449²⁺²=449²⋅449² ≡ 640⋅640=409600 ≡ 235 mod 827

8: 449⁸=449⁴⁺⁴=449⁴⋅449⁴ ≡ 235⋅235=55225 ≡ 643 mod 827

16: 449¹⁶=449⁸⁺⁸=449⁸⋅449⁸ ≡ 643⋅643=413449 ≡ 776 mod 827

32: 449³²=449¹⁶⁺¹⁶=449¹⁶⋅449¹⁶ ≡ 776⋅776=602176 ≡ 120 mod 827

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

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

245 = 128+64+32+16+4+1

639²⁴⁵

= 639^{128+64+32+16+4+1}

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

≡ 606 ⋅ 599 ⋅ 646 ⋅ 167 ⋅ 40 ⋅ 639 mod 1009
≡ 362994 ⋅ 646 ⋅ 167 ⋅ 40 ⋅ 639 mod 1009 ≡ 763 ⋅ 646 ⋅ 167 ⋅ 40 ⋅ 639 mod 1009
≡ 492898 ⋅ 167 ⋅ 40 ⋅ 639 mod 1009 ≡ 506 ⋅ 167 ⋅ 40 ⋅ 639 mod 1009
≡ 84502 ⋅ 40 ⋅ 639 mod 1009 ≡ 755 ⋅ 40 ⋅ 639 mod 1009
≡ 30200 ⋅ 639 mod 1009 ≡ 939 ⋅ 639 mod 1009
≡ 600021 mod 1009 ≡ 675 mod 1009

Es gilt also: 639²⁴⁵ ≡ 675 mod 1009

Berechnung des größten gemeinsamen Teilers von 73 und 26

=>73	= 2⋅26 + 21
=>26	= 1⋅21 + 5
=>21	= 4⋅5 + 1
=>5	= 5⋅1 + 0

also gilt: ggt(73,26)=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= 21-4⋅5
5= 26-1⋅21	eingesetzt in die Zeile drüber:	1	= 1⋅21 -4⋅(26 -1⋅ 21) = 1⋅21 -4⋅26 +4⋅ 21) = -4⋅26 +5⋅ 21 (=1)
21= 73-2⋅26	eingesetzt in die Zeile drüber:	1	= -4⋅26 +5⋅(73 -2⋅ 26) = -4⋅26 +5⋅73 -10⋅ 26) = 5⋅73 -14⋅ 26 (=1)

Es gilt also: ggt(73,26)=1 = 5⋅73 -14⋅26

oder wenn man 5⋅73 auf die linke Seite bringt:

1 -5⋅73 = -14⋅26

-14⋅26 = -5⋅73 + 1 |+73⋅26

-14⋅26 + 73⋅26 = -5⋅73 + 73⋅26 + 1

(-14 + 73) ⋅ 26 = (-5 + 26) ⋅ 73 + 1

59⋅26 = 21⋅73 + 1

Es gilt also: 59⋅26 = 21⋅73 +1

Somit 59⋅26 = 1 mod 73

59 ist also das Inverse von 26 mod 73