Um längere Rechnungen zu vermeiden, rechnen wir:

(125 + 2400) mod 6 ≡ (125 mod 6 + 2400 mod 6) mod 6.

125 mod 6 ≡ 5 mod 6 kann man relativ leicht bestimmen, weil ja 125 = 120+5 = 6 ⋅ 20 +5.

2400 mod 6 ≡ 0 mod 6 kann man relativ leicht bestimmen, weil ja 2400 = 2400+0 = 6 ⋅ 400 +0.

Somit gilt:

(125 + 2400) mod 6 ≡ (5 + 0) mod 6 ≡ 5 mod 6.

Um längere Rechnungen zu vermeiden, rechnen wir:

(30 ⋅ 79) mod 4 ≡ (30 mod 4 ⋅ 79 mod 4) mod 4.

30 mod 4 ≡ 2 mod 4 kann man relativ leicht bestimmen, weil ja 30 = 28 + 2 = 7 ⋅ 4 + 2 ist.

79 mod 4 ≡ 3 mod 4 kann man relativ leicht bestimmen, weil ja 79 = 76 + 3 = 19 ⋅ 4 + 3 ist.

Somit gilt:

(30 ⋅ 79) mod 4 ≡ (2 ⋅ 3) mod 4 ≡ 6 mod 4 ≡ 2 mod 4.

Die 64 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: 716¹=716

2: 716²=716¹⁺¹=716¹⋅716¹ ≡ 716⋅716=512656 ≡ 752 mod 941

4: 716⁴=716²⁺²=716²⋅716² ≡ 752⋅752=565504 ≡ 904 mod 941

8: 716⁸=716⁴⁺⁴=716⁴⋅716⁴ ≡ 904⋅904=817216 ≡ 428 mod 941

16: 716¹⁶=716⁸⁺⁸=716⁸⋅716⁸ ≡ 428⋅428=183184 ≡ 630 mod 941

32: 716³²=716¹⁶⁺¹⁶=716¹⁶⋅716¹⁶ ≡ 630⋅630=396900 ≡ 739 mod 941

64: 716⁶⁴=716³²⁺³²=716³²⋅716³² ≡ 739⋅739=546121 ≡ 341 mod 941

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

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

179 = 128+32+16+2+1

249¹⁷⁹

= 249^{128+32+16+2+1}

= 249¹²⁸⋅249³²⋅249¹⁶⋅249²⋅249¹

≡ 335 ⋅ 269 ⋅ 139 ⋅ 82 ⋅ 249 mod 433
≡ 90115 ⋅ 139 ⋅ 82 ⋅ 249 mod 433 ≡ 51 ⋅ 139 ⋅ 82 ⋅ 249 mod 433
≡ 7089 ⋅ 82 ⋅ 249 mod 433 ≡ 161 ⋅ 82 ⋅ 249 mod 433
≡ 13202 ⋅ 249 mod 433 ≡ 212 ⋅ 249 mod 433
≡ 52788 mod 433 ≡ 395 mod 433

Es gilt also: 249¹⁷⁹ ≡ 395 mod 433

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

=>89	= 1⋅83 + 6
=>83	= 13⋅6 + 5
=>6	= 1⋅5 + 1
=>5	= 5⋅1 + 0

also gilt: ggt(89,83)=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= 83-13⋅6	eingesetzt in die Zeile drüber:	1	= 1⋅6 -1⋅(83 -13⋅ 6) = 1⋅6 -1⋅83 +13⋅ 6) = -1⋅83 +14⋅ 6 (=1)
6= 89-1⋅83	eingesetzt in die Zeile drüber:	1	= -1⋅83 +14⋅(89 -1⋅ 83) = -1⋅83 +14⋅89 -14⋅ 83) = 14⋅89 -15⋅ 83 (=1)

Es gilt also: ggt(89,83)=1 = 14⋅89 -15⋅83

oder wenn man 14⋅89 auf die linke Seite bringt:

1 -14⋅89 = -15⋅83

-15⋅83 = -14⋅89 + 1 |+89⋅83

-15⋅83 + 89⋅83 = -14⋅89 + 89⋅83 + 1

(-15 + 89) ⋅ 83 = (-14 + 83) ⋅ 89 + 1

74⋅83 = 69⋅89 + 1

Es gilt also: 74⋅83 = 69⋅89 +1

Somit 74⋅83 = 1 mod 89

74 ist also das Inverse von 83 mod 89