Um längere Rechnungen zu vermeiden, rechnen wir:

(1200 - 183) mod 6 ≡ (1200 mod 6 - 183 mod 6) mod 6.

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

183 mod 6 ≡ 3 mod 6 kann man relativ leicht bestimmen, weil ja 183 = 180+3 = 6 ⋅ 30 +3.

Somit gilt:

(1200 - 183) mod 6 ≡ (0 - 3) mod 6 ≡ -3 mod 6 ≡ 3 mod 6.

Um längere Rechnungen zu vermeiden, rechnen wir:

(41 ⋅ 46) mod 11 ≡ (41 mod 11 ⋅ 46 mod 11) mod 11.

41 mod 11 ≡ 8 mod 11 kann man relativ leicht bestimmen, weil ja 41 = 33 + 8 = 3 ⋅ 11 + 8 ist.

46 mod 11 ≡ 2 mod 11 kann man relativ leicht bestimmen, weil ja 46 = 44 + 2 = 4 ⋅ 11 + 2 ist.

Somit gilt:

(41 ⋅ 46) mod 11 ≡ (8 ⋅ 2) mod 11 ≡ 16 mod 11 ≡ 5 mod 11.

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

2: 706²=706¹⁺¹=706¹⋅706¹ ≡ 706⋅706=498436 ≡ 166 mod 977

4: 706⁴=706²⁺²=706²⋅706² ≡ 166⋅166=27556 ≡ 200 mod 977

8: 706⁸=706⁴⁺⁴=706⁴⋅706⁴ ≡ 200⋅200=40000 ≡ 920 mod 977

16: 706¹⁶=706⁸⁺⁸=706⁸⋅706⁸ ≡ 920⋅920=846400 ≡ 318 mod 977

32: 706³²=706¹⁶⁺¹⁶=706¹⁶⋅706¹⁶ ≡ 318⋅318=101124 ≡ 493 mod 977

64: 706⁶⁴=706³²⁺³²=706³²⋅706³² ≡ 493⋅493=243049 ≡ 753 mod 977

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

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

225 = 128+64+32+1

103²²⁵

= 103^128+64+32+1

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

≡ 98 ⋅ 87 ⋅ 91 ⋅ 103 mod 241
≡ 8526 ⋅ 91 ⋅ 103 mod 241 ≡ 91 ⋅ 91 ⋅ 103 mod 241
≡ 8281 ⋅ 103 mod 241 ≡ 87 ⋅ 103 mod 241
≡ 8961 mod 241 ≡ 44 mod 241

Es gilt also: 103²²⁵ ≡ 44 mod 241

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

=>83	= 1⋅55 + 28
=>55	= 1⋅28 + 27
=>28	= 1⋅27 + 1
=>27	= 27⋅1 + 0

also gilt: ggt(83,55)=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= 28-1⋅27
27= 55-1⋅28	eingesetzt in die Zeile drüber:	1	= 1⋅28 -1⋅(55 -1⋅ 28) = 1⋅28 -1⋅55 +1⋅ 28) = -1⋅55 +2⋅ 28 (=1)
28= 83-1⋅55	eingesetzt in die Zeile drüber:	1	= -1⋅55 +2⋅(83 -1⋅ 55) = -1⋅55 +2⋅83 -2⋅ 55) = 2⋅83 -3⋅ 55 (=1)

Es gilt also: ggt(83,55)=1 = 2⋅83 -3⋅55

oder wenn man 2⋅83 auf die linke Seite bringt:

1 -2⋅83 = -3⋅55

-3⋅55 = -2⋅83 + 1 |+83⋅55

-3⋅55 + 83⋅55 = -2⋅83 + 83⋅55 + 1

(-3 + 83) ⋅ 55 = (-2 + 55) ⋅ 83 + 1

80⋅55 = 53⋅83 + 1

Es gilt also: 80⋅55 = 53⋅83 +1

Somit 80⋅55 = 1 mod 83

80 ist also das Inverse von 55 mod 83