Um längere Rechnungen zu vermeiden, rechnen wir:

(18003 + 270) mod 9 ≡ (18003 mod 9 + 270 mod 9) mod 9.

18003 mod 9 ≡ 3 mod 9 kann man relativ leicht bestimmen, weil ja 18003 = 18000+3 = 9 ⋅ 2000 +3.

270 mod 9 ≡ 0 mod 9 kann man relativ leicht bestimmen, weil ja 270 = 270+0 = 9 ⋅ 30 +0.

Somit gilt:

(18003 + 270) mod 9 ≡ (3 + 0) mod 9 ≡ 3 mod 9.

Um längere Rechnungen zu vermeiden, rechnen wir:

(73 ⋅ 16) mod 6 ≡ (73 mod 6 ⋅ 16 mod 6) mod 6.

73 mod 6 ≡ 1 mod 6 kann man relativ leicht bestimmen, weil ja 73 = 72 + 1 = 12 ⋅ 6 + 1 ist.

16 mod 6 ≡ 4 mod 6 kann man relativ leicht bestimmen, weil ja 16 = 12 + 4 = 2 ⋅ 6 + 4 ist.

Somit gilt:

(73 ⋅ 16) mod 6 ≡ (1 ⋅ 4) mod 6 ≡ 4 mod 6.

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

2: 132²=132¹⁺¹=132¹⋅132¹ ≡ 132⋅132=17424 ≡ 250 mod 277

4: 132⁴=132²⁺²=132²⋅132² ≡ 250⋅250=62500 ≡ 175 mod 277

8: 132⁸=132⁴⁺⁴=132⁴⋅132⁴ ≡ 175⋅175=30625 ≡ 155 mod 277

16: 132¹⁶=132⁸⁺⁸=132⁸⋅132⁸ ≡ 155⋅155=24025 ≡ 203 mod 277

32: 132³²=132¹⁶⁺¹⁶=132¹⁶⋅132¹⁶ ≡ 203⋅203=41209 ≡ 213 mod 277

64: 132⁶⁴=132³²⁺³²=132³²⋅132³² ≡ 213⋅213=45369 ≡ 218 mod 277

128: 132¹²⁸=132⁶⁴⁺⁶⁴=132⁶⁴⋅132⁶⁴ ≡ 218⋅218=47524 ≡ 157 mod 277

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

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

231 = 128+64+32+4+2+1

211²³¹

= 211^{128+64+32+4+2+1}

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

≡ 198 ⋅ 383 ⋅ 139 ⋅ 407 ⋅ 518 ⋅ 211 mod 557
≡ 75834 ⋅ 139 ⋅ 407 ⋅ 518 ⋅ 211 mod 557 ≡ 82 ⋅ 139 ⋅ 407 ⋅ 518 ⋅ 211 mod 557
≡ 11398 ⋅ 407 ⋅ 518 ⋅ 211 mod 557 ≡ 258 ⋅ 407 ⋅ 518 ⋅ 211 mod 557
≡ 105006 ⋅ 518 ⋅ 211 mod 557 ≡ 290 ⋅ 518 ⋅ 211 mod 557
≡ 150220 ⋅ 211 mod 557 ≡ 387 ⋅ 211 mod 557
≡ 81657 mod 557 ≡ 335 mod 557

Es gilt also: 211²³¹ ≡ 335 mod 557

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

=>83	= 2⋅38 + 7
=>38	= 5⋅7 + 3
=>7	= 2⋅3 + 1
=>3	= 3⋅1 + 0

also gilt: ggt(83,38)=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= 7-2⋅3
3= 38-5⋅7	eingesetzt in die Zeile drüber:	1	= 1⋅7 -2⋅(38 -5⋅ 7) = 1⋅7 -2⋅38 +10⋅ 7) = -2⋅38 +11⋅ 7 (=1)
7= 83-2⋅38	eingesetzt in die Zeile drüber:	1	= -2⋅38 +11⋅(83 -2⋅ 38) = -2⋅38 +11⋅83 -22⋅ 38) = 11⋅83 -24⋅ 38 (=1)

Es gilt also: ggt(83,38)=1 = 11⋅83 -24⋅38

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

1 -11⋅83 = -24⋅38

-24⋅38 = -11⋅83 + 1 |+83⋅38

-24⋅38 + 83⋅38 = -11⋅83 + 83⋅38 + 1

(-24 + 83) ⋅ 38 = (-11 + 38) ⋅ 83 + 1

59⋅38 = 27⋅83 + 1

Es gilt also: 59⋅38 = 27⋅83 +1

Somit 59⋅38 = 1 mod 83

59 ist also das Inverse von 38 mod 83