Um längere Rechnungen zu vermeiden, rechnen wir:

(7001 - 3499) mod 7 ≡ (7001 mod 7 - 3499 mod 7) mod 7.

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

3499 mod 7 ≡ 6 mod 7 kann man relativ leicht bestimmen, weil ja 3499 = 3500-1 = 7 ⋅ 500 -1 = 7 ⋅ 500 - 7 + 6.

Somit gilt:

(7001 - 3499) mod 7 ≡ (1 - 6) mod 7 ≡ -5 mod 7 ≡ 2 mod 7.

Um längere Rechnungen zu vermeiden, rechnen wir:

(60 ⋅ 65) mod 8 ≡ (60 mod 8 ⋅ 65 mod 8) mod 8.

60 mod 8 ≡ 4 mod 8 kann man relativ leicht bestimmen, weil ja 60 = 56 + 4 = 7 ⋅ 8 + 4 ist.

65 mod 8 ≡ 1 mod 8 kann man relativ leicht bestimmen, weil ja 65 = 64 + 1 = 8 ⋅ 8 + 1 ist.

Somit gilt:

(60 ⋅ 65) mod 8 ≡ (4 ⋅ 1) mod 8 ≡ 4 mod 8.

Die 8 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: 304¹=304

2: 304²=304¹⁺¹=304¹⋅304¹ ≡ 304⋅304=92416 ≡ 467 mod 643

4: 304⁴=304²⁺²=304²⋅304² ≡ 467⋅467=218089 ≡ 112 mod 643

8: 304⁸=304⁴⁺⁴=304⁴⋅304⁴ ≡ 112⋅112=12544 ≡ 327 mod 643

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

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

126 = 64+32+16+8+4+2

782¹²⁶

= 782^{64+32+16+8+4+2}

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

≡ 658 ⋅ 282 ⋅ 411 ⋅ 114 ⋅ 542 ⋅ 732 mod 839
≡ 185556 ⋅ 411 ⋅ 114 ⋅ 542 ⋅ 732 mod 839 ≡ 137 ⋅ 411 ⋅ 114 ⋅ 542 ⋅ 732 mod 839
≡ 56307 ⋅ 114 ⋅ 542 ⋅ 732 mod 839 ≡ 94 ⋅ 114 ⋅ 542 ⋅ 732 mod 839
≡ 10716 ⋅ 542 ⋅ 732 mod 839 ≡ 648 ⋅ 542 ⋅ 732 mod 839
≡ 351216 ⋅ 732 mod 839 ≡ 514 ⋅ 732 mod 839
≡ 376248 mod 839 ≡ 376 mod 839

Es gilt also: 782¹²⁶ ≡ 376 mod 839

Berechnung des größten gemeinsamen Teilers von 59 und 53

=>59	= 1⋅53 + 6
=>53	= 8⋅6 + 5
=>6	= 1⋅5 + 1
=>5	= 5⋅1 + 0

also gilt: ggt(59,53)=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= 53-8⋅6	eingesetzt in die Zeile drüber:	1	= 1⋅6 -1⋅(53 -8⋅ 6) = 1⋅6 -1⋅53 +8⋅ 6) = -1⋅53 +9⋅ 6 (=1)
6= 59-1⋅53	eingesetzt in die Zeile drüber:	1	= -1⋅53 +9⋅(59 -1⋅ 53) = -1⋅53 +9⋅59 -9⋅ 53) = 9⋅59 -10⋅ 53 (=1)

Es gilt also: ggt(59,53)=1 = 9⋅59 -10⋅53

oder wenn man 9⋅59 auf die linke Seite bringt:

1 -9⋅59 = -10⋅53

-10⋅53 = -9⋅59 + 1 |+59⋅53

-10⋅53 + 59⋅53 = -9⋅59 + 59⋅53 + 1

(-10 + 59) ⋅ 53 = (-9 + 53) ⋅ 59 + 1

49⋅53 = 44⋅59 + 1

Es gilt also: 49⋅53 = 44⋅59 +1

Somit 49⋅53 = 1 mod 59

49 ist also das Inverse von 53 mod 59