Um längere Rechnungen zu vermeiden, rechnen wir:

(150 + 1203) mod 3 ≡ (150 mod 3 + 1203 mod 3) mod 3.

150 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 150 = 150+0 = 3 ⋅ 50 +0.

1203 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 1203 = 1200+3 = 3 ⋅ 400 +3.

Somit gilt:

(150 + 1203) mod 3 ≡ (0 + 0) mod 3 ≡ 0 mod 3.

Um längere Rechnungen zu vermeiden, rechnen wir:

(87 ⋅ 28) mod 3 ≡ (87 mod 3 ⋅ 28 mod 3) mod 3.

87 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 87 = 87 + 0 = 29 ⋅ 3 + 0 ist.

28 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 28 = 27 + 1 = 9 ⋅ 3 + 1 ist.

Somit gilt:

(87 ⋅ 28) mod 3 ≡ (0 ⋅ 1) mod 3 ≡ 0 mod 3.

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

2: 825²=825¹⁺¹=825¹⋅825¹ ≡ 825⋅825=680625 ≡ 297 mod 859

4: 825⁴=825²⁺²=825²⋅825² ≡ 297⋅297=88209 ≡ 591 mod 859

8: 825⁸=825⁴⁺⁴=825⁴⋅825⁴ ≡ 591⋅591=349281 ≡ 527 mod 859

16: 825¹⁶=825⁸⁺⁸=825⁸⋅825⁸ ≡ 527⋅527=277729 ≡ 272 mod 859

32: 825³²=825¹⁶⁺¹⁶=825¹⁶⋅825¹⁶ ≡ 272⋅272=73984 ≡ 110 mod 859

64: 825⁶⁴=825³²⁺³²=825³²⋅825³² ≡ 110⋅110=12100 ≡ 74 mod 859

128: 825¹²⁸=825⁶⁴⁺⁶⁴=825⁶⁴⋅825⁶⁴ ≡ 74⋅74=5476 ≡ 322 mod 859

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

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

149 = 128+16+4+1

147¹⁴⁹

= 147^128+16+4+1

= 147¹²⁸⋅147¹⁶⋅147⁴⋅147¹

≡ 196 ⋅ 290 ⋅ 230 ⋅ 147 mod 331
≡ 56840 ⋅ 230 ⋅ 147 mod 331 ≡ 239 ⋅ 230 ⋅ 147 mod 331
≡ 54970 ⋅ 147 mod 331 ≡ 24 ⋅ 147 mod 331
≡ 3528 mod 331 ≡ 218 mod 331

Es gilt also: 147¹⁴⁹ ≡ 218 mod 331

Berechnung des größten gemeinsamen Teilers von 73 und 35

=>73	= 2⋅35 + 3
=>35	= 11⋅3 + 2
=>3	= 1⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(73,35)=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= 3-1⋅2
2= 35-11⋅3	eingesetzt in die Zeile drüber:	1	= 1⋅3 -1⋅(35 -11⋅ 3) = 1⋅3 -1⋅35 +11⋅ 3) = -1⋅35 +12⋅ 3 (=1)
3= 73-2⋅35	eingesetzt in die Zeile drüber:	1	= -1⋅35 +12⋅(73 -2⋅ 35) = -1⋅35 +12⋅73 -24⋅ 35) = 12⋅73 -25⋅ 35 (=1)

Es gilt also: ggt(73,35)=1 = 12⋅73 -25⋅35

oder wenn man 12⋅73 auf die linke Seite bringt:

1 -12⋅73 = -25⋅35

-25⋅35 = -12⋅73 + 1 |+73⋅35

-25⋅35 + 73⋅35 = -12⋅73 + 73⋅35 + 1

(-25 + 73) ⋅ 35 = (-12 + 35) ⋅ 73 + 1

48⋅35 = 23⋅73 + 1

Es gilt also: 48⋅35 = 23⋅73 +1

Somit 48⋅35 = 1 mod 73

48 ist also das Inverse von 35 mod 73