Um längere Rechnungen zu vermeiden, rechnen wir:

(7999 - 1200) mod 4 ≡ (7999 mod 4 - 1200 mod 4) mod 4.

7999 mod 4 ≡ 3 mod 4 kann man relativ leicht bestimmen, weil ja 7999 = 7000+999 = 4 ⋅ 1750 +999.

1200 mod 4 ≡ 0 mod 4 kann man relativ leicht bestimmen, weil ja 1200 = 1200+0 = 4 ⋅ 300 +0.

Somit gilt:

(7999 - 1200) mod 4 ≡ (3 - 0) mod 4 ≡ 3 mod 4.

Um längere Rechnungen zu vermeiden, rechnen wir:

(36 ⋅ 16) mod 7 ≡ (36 mod 7 ⋅ 16 mod 7) mod 7.

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

16 mod 7 ≡ 2 mod 7 kann man relativ leicht bestimmen, weil ja 16 = 14 + 2 = 2 ⋅ 7 + 2 ist.

Somit gilt:

(36 ⋅ 16) mod 7 ≡ (1 ⋅ 2) mod 7 ≡ 2 mod 7.

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: 206¹=206

2: 206²=206¹⁺¹=206¹⋅206¹ ≡ 206⋅206=42436 ≡ 70 mod 307

4: 206⁴=206²⁺²=206²⋅206² ≡ 70⋅70=4900 ≡ 295 mod 307

8: 206⁸=206⁴⁺⁴=206⁴⋅206⁴ ≡ 295⋅295=87025 ≡ 144 mod 307

16: 206¹⁶=206⁸⁺⁸=206⁸⋅206⁸ ≡ 144⋅144=20736 ≡ 167 mod 307

32: 206³²=206¹⁶⁺¹⁶=206¹⁶⋅206¹⁶ ≡ 167⋅167=27889 ≡ 259 mod 307

64: 206⁶⁴=206³²⁺³²=206³²⋅206³² ≡ 259⋅259=67081 ≡ 155 mod 307

128: 206¹²⁸=206⁶⁴⁺⁶⁴=206⁶⁴⋅206⁶⁴ ≡ 155⋅155=24025 ≡ 79 mod 307

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

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

114 = 64+32+16+2

274¹¹⁴

= 274^64+32+16+2

= 274⁶⁴⋅274³²⋅274¹⁶⋅274²

≡ 168 ⋅ 66 ⋅ 88 ⋅ 41 mod 349
≡ 11088 ⋅ 88 ⋅ 41 mod 349 ≡ 269 ⋅ 88 ⋅ 41 mod 349
≡ 23672 ⋅ 41 mod 349 ≡ 289 ⋅ 41 mod 349
≡ 11849 mod 349 ≡ 332 mod 349

Es gilt also: 274¹¹⁴ ≡ 332 mod 349

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

=>101	= 1⋅89 + 12
=>89	= 7⋅12 + 5
=>12	= 2⋅5 + 2
=>5	= 2⋅2 + 1
=>2	= 2⋅1 + 0

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

Es gilt also: ggt(101,89)=1 = -37⋅101 +42⋅89

oder wenn man -37⋅101 auf die linke Seite bringt:

1 +37⋅101 = +42⋅89

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

Somit 42⋅89 = 1 mod 101

42 ist also das Inverse von 89 mod 101