Um längere Rechnungen zu vermeiden, rechnen wir:

(7002 - 3497) mod 7 ≡ (7002 mod 7 - 3497 mod 7) mod 7.

7002 mod 7 ≡ 2 mod 7 kann man relativ leicht bestimmen, weil ja 7002 = 7000+2 = 7 ⋅ 1000 +2.

3497 mod 7 ≡ 4 mod 7 kann man relativ leicht bestimmen, weil ja 3497 = 3500-3 = 7 ⋅ 500 -3 = 7 ⋅ 500 - 7 + 4.

Somit gilt:

(7002 - 3497) mod 7 ≡ (2 - 4) mod 7 ≡ -2 mod 7 ≡ 5 mod 7.

Um längere Rechnungen zu vermeiden, rechnen wir:

(100 ⋅ 16) mod 3 ≡ (100 mod 3 ⋅ 16 mod 3) mod 3.

100 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 100 = 99 + 1 = 33 ⋅ 3 + 1 ist.

16 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 16 = 15 + 1 = 5 ⋅ 3 + 1 ist.

Somit gilt:

(100 ⋅ 16) mod 3 ≡ (1 ⋅ 1) mod 3 ≡ 1 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: 329¹=329

2: 329²=329¹⁺¹=329¹⋅329¹ ≡ 329⋅329=108241 ≡ 552 mod 953

4: 329⁴=329²⁺²=329²⋅329² ≡ 552⋅552=304704 ≡ 697 mod 953

8: 329⁸=329⁴⁺⁴=329⁴⋅329⁴ ≡ 697⋅697=485809 ≡ 732 mod 953

16: 329¹⁶=329⁸⁺⁸=329⁸⋅329⁸ ≡ 732⋅732=535824 ≡ 238 mod 953

32: 329³²=329¹⁶⁺¹⁶=329¹⁶⋅329¹⁶ ≡ 238⋅238=56644 ≡ 417 mod 953

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

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

251 = 128+64+32+16+8+2+1

679²⁵¹

= 679^{128+64+32+16+8+2+1}

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

≡ 557 ⋅ 371 ⋅ 66 ⋅ 217 ⋅ 277 ⋅ 375 ⋅ 679 mod 797
≡ 206647 ⋅ 66 ⋅ 217 ⋅ 277 ⋅ 375 ⋅ 679 mod 797 ≡ 224 ⋅ 66 ⋅ 217 ⋅ 277 ⋅ 375 ⋅ 679 mod 797
≡ 14784 ⋅ 217 ⋅ 277 ⋅ 375 ⋅ 679 mod 797 ≡ 438 ⋅ 217 ⋅ 277 ⋅ 375 ⋅ 679 mod 797
≡ 95046 ⋅ 277 ⋅ 375 ⋅ 679 mod 797 ≡ 203 ⋅ 277 ⋅ 375 ⋅ 679 mod 797
≡ 56231 ⋅ 375 ⋅ 679 mod 797 ≡ 441 ⋅ 375 ⋅ 679 mod 797
≡ 165375 ⋅ 679 mod 797 ≡ 396 ⋅ 679 mod 797
≡ 268884 mod 797 ≡ 295 mod 797

Es gilt also: 679²⁵¹ ≡ 295 mod 797

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

=>73	= 3⋅23 + 4
=>23	= 5⋅4 + 3
=>4	= 1⋅3 + 1
=>3	= 3⋅1 + 0

also gilt: ggt(73,23)=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= 23-5⋅4	eingesetzt in die Zeile drüber:	1	= 1⋅4 -1⋅(23 -5⋅ 4) = 1⋅4 -1⋅23 +5⋅ 4) = -1⋅23 +6⋅ 4 (=1)
4= 73-3⋅23	eingesetzt in die Zeile drüber:	1	= -1⋅23 +6⋅(73 -3⋅ 23) = -1⋅23 +6⋅73 -18⋅ 23) = 6⋅73 -19⋅ 23 (=1)

Es gilt also: ggt(73,23)=1 = 6⋅73 -19⋅23

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

1 -6⋅73 = -19⋅23

-19⋅23 = -6⋅73 + 1 |+73⋅23

-19⋅23 + 73⋅23 = -6⋅73 + 73⋅23 + 1

(-19 + 73) ⋅ 23 = (-6 + 23) ⋅ 73 + 1

54⋅23 = 17⋅73 + 1

Es gilt also: 54⋅23 = 17⋅73 +1

Somit 54⋅23 = 1 mod 73

54 ist also das Inverse von 23 mod 73