Um längere Rechnungen zu vermeiden, rechnen wir:

(5997 + 6003) mod 6 ≡ (5997 mod 6 + 6003 mod 6) mod 6.

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

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

Somit gilt:

(5997 + 6003) mod 6 ≡ (3 + 3) mod 6 ≡ 6 mod 6 ≡ 0 mod 6.

Um längere Rechnungen zu vermeiden, rechnen wir:

(35 ⋅ 99) mod 7 ≡ (35 mod 7 ⋅ 99 mod 7) mod 7.

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

99 mod 7 ≡ 1 mod 7 kann man relativ leicht bestimmen, weil ja 99 = 98 + 1 = 14 ⋅ 7 + 1 ist.

Somit gilt:

(35 ⋅ 99) mod 7 ≡ (0 ⋅ 1) mod 7 ≡ 0 mod 7.

Die 16 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: 481¹=481

2: 481²=481¹⁺¹=481¹⋅481¹ ≡ 481⋅481=231361 ≡ 70 mod 829

4: 481⁴=481²⁺²=481²⋅481² ≡ 70⋅70=4900 ≡ 755 mod 829

8: 481⁸=481⁴⁺⁴=481⁴⋅481⁴ ≡ 755⋅755=570025 ≡ 502 mod 829

16: 481¹⁶=481⁸⁺⁸=481⁸⋅481⁸ ≡ 502⋅502=252004 ≡ 817 mod 829

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

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

213 = 128+64+16+4+1

414²¹³

= 414^{128+64+16+4+1}

= 414¹²⁸⋅414⁶⁴⋅414¹⁶⋅414⁴⋅414¹

≡ 126 ⋅ 25 ⋅ 449 ⋅ 235 ⋅ 414 mod 499
≡ 3150 ⋅ 449 ⋅ 235 ⋅ 414 mod 499 ≡ 156 ⋅ 449 ⋅ 235 ⋅ 414 mod 499
≡ 70044 ⋅ 235 ⋅ 414 mod 499 ≡ 184 ⋅ 235 ⋅ 414 mod 499
≡ 43240 ⋅ 414 mod 499 ≡ 326 ⋅ 414 mod 499
≡ 134964 mod 499 ≡ 234 mod 499

Es gilt also: 414²¹³ ≡ 234 mod 499

Berechnung des größten gemeinsamen Teilers von 71 und 65

=>71	= 1⋅65 + 6
=>65	= 10⋅6 + 5
=>6	= 1⋅5 + 1
=>5	= 5⋅1 + 0

also gilt: ggt(71,65)=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= 6-1⋅5
5= 65-10⋅6	eingesetzt in die Zeile drüber:	1	= 1⋅6 -1⋅(65 -10⋅ 6) = 1⋅6 -1⋅65 +10⋅ 6) = -1⋅65 +11⋅ 6 (=1)
6= 71-1⋅65	eingesetzt in die Zeile drüber:	1	= -1⋅65 +11⋅(71 -1⋅ 65) = -1⋅65 +11⋅71 -11⋅ 65) = 11⋅71 -12⋅ 65 (=1)

Es gilt also: ggt(71,65)=1 = 11⋅71 -12⋅65

oder wenn man 11⋅71 auf die linke Seite bringt:

1 -11⋅71 = -12⋅65

-12⋅65 = -11⋅71 + 1 |+71⋅65

-12⋅65 + 71⋅65 = -11⋅71 + 71⋅65 + 1

(-12 + 71) ⋅ 65 = (-11 + 65) ⋅ 71 + 1

59⋅65 = 54⋅71 + 1

Es gilt also: 59⋅65 = 54⋅71 +1

Somit 59⋅65 = 1 mod 71

59 ist also das Inverse von 65 mod 71