Um längere Rechnungen zu vermeiden, rechnen wir:

(14006 - 3506) mod 7 ≡ (14006 mod 7 - 3506 mod 7) mod 7.

14006 mod 7 ≡ 6 mod 7 kann man relativ leicht bestimmen, weil ja 14006 = 14000+6 = 7 ⋅ 2000 +6.

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

Somit gilt:

(14006 - 3506) mod 7 ≡ (6 - 6) mod 7 ≡ 0 mod 7.

Um längere Rechnungen zu vermeiden, rechnen wir:

(23 ⋅ 17) mod 11 ≡ (23 mod 11 ⋅ 17 mod 11) mod 11.

23 mod 11 ≡ 1 mod 11 kann man relativ leicht bestimmen, weil ja 23 = 22 + 1 = 2 ⋅ 11 + 1 ist.

17 mod 11 ≡ 6 mod 11 kann man relativ leicht bestimmen, weil ja 17 = 11 + 6 = 1 ⋅ 11 + 6 ist.

Somit gilt:

(23 ⋅ 17) mod 11 ≡ (1 ⋅ 6) mod 11 ≡ 6 mod 11.

Die 128 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: 583¹=583

2: 583²=583¹⁺¹=583¹⋅583¹ ≡ 583⋅583=339889 ≡ 278 mod 709

4: 583⁴=583²⁺²=583²⋅583² ≡ 278⋅278=77284 ≡ 3 mod 709

8: 583⁸=583⁴⁺⁴=583⁴⋅583⁴ ≡ 3⋅3=9 ≡ 9 mod 709

16: 583¹⁶=583⁸⁺⁸=583⁸⋅583⁸ ≡ 9⋅9=81 ≡ 81 mod 709

32: 583³²=583¹⁶⁺¹⁶=583¹⁶⋅583¹⁶ ≡ 81⋅81=6561 ≡ 180 mod 709

64: 583⁶⁴=583³²⁺³²=583³²⋅583³² ≡ 180⋅180=32400 ≡ 495 mod 709

128: 583¹²⁸=583⁶⁴⁺⁶⁴=583⁶⁴⋅583⁶⁴ ≡ 495⋅495=245025 ≡ 420 mod 709

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

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

71 = 64+4+2+1

129⁷¹

= 129^64+4+2+1

= 129⁶⁴⋅129⁴⋅129²⋅129¹

≡ 38 ⋅ 84 ⋅ 233 ⋅ 129 mod 293
≡ 3192 ⋅ 233 ⋅ 129 mod 293 ≡ 262 ⋅ 233 ⋅ 129 mod 293
≡ 61046 ⋅ 129 mod 293 ≡ 102 ⋅ 129 mod 293
≡ 13158 mod 293 ≡ 266 mod 293

Es gilt also: 129⁷¹ ≡ 266 mod 293

Berechnung des größten gemeinsamen Teilers von 101 und 42

=>101	= 2⋅42 + 17
=>42	= 2⋅17 + 8
=>17	= 2⋅8 + 1
=>8	= 8⋅1 + 0

also gilt: ggt(101,42)=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= 17-2⋅8
8= 42-2⋅17	eingesetzt in die Zeile drüber:	1	= 1⋅17 -2⋅(42 -2⋅ 17) = 1⋅17 -2⋅42 +4⋅ 17) = -2⋅42 +5⋅ 17 (=1)
17= 101-2⋅42	eingesetzt in die Zeile drüber:	1	= -2⋅42 +5⋅(101 -2⋅ 42) = -2⋅42 +5⋅101 -10⋅ 42) = 5⋅101 -12⋅ 42 (=1)

Es gilt also: ggt(101,42)=1 = 5⋅101 -12⋅42

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

1 -5⋅101 = -12⋅42

-12⋅42 = -5⋅101 + 1 |+101⋅42

-12⋅42 + 101⋅42 = -5⋅101 + 101⋅42 + 1

(-12 + 101) ⋅ 42 = (-5 + 42) ⋅ 101 + 1

89⋅42 = 37⋅101 + 1

Es gilt also: 89⋅42 = 37⋅101 +1

Somit 89⋅42 = 1 mod 101

89 ist also das Inverse von 42 mod 101