Um längere Rechnungen zu vermeiden, rechnen wir:

(27000 + 178) mod 9 ≡ (27000 mod 9 + 178 mod 9) mod 9.

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

178 mod 9 ≡ 7 mod 9 kann man relativ leicht bestimmen, weil ja 178 = 180-2 = 9 ⋅ 20 -2 = 9 ⋅ 20 - 9 + 7.

Somit gilt:

(27000 + 178) mod 9 ≡ (0 + 7) mod 9 ≡ 7 mod 9.

Um längere Rechnungen zu vermeiden, rechnen wir:

(95 ⋅ 17) mod 3 ≡ (95 mod 3 ⋅ 17 mod 3) mod 3.

95 mod 3 ≡ 2 mod 3 kann man relativ leicht bestimmen, weil ja 95 = 93 + 2 = 31 ⋅ 3 + 2 ist.

17 mod 3 ≡ 2 mod 3 kann man relativ leicht bestimmen, weil ja 17 = 15 + 2 = 5 ⋅ 3 + 2 ist.

Somit gilt:

(95 ⋅ 17) mod 3 ≡ (2 ⋅ 2) mod 3 ≡ 4 mod 3 ≡ 1 mod 3.

Die 16 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: 408¹=408

2: 408²=408¹⁺¹=408¹⋅408¹ ≡ 408⋅408=166464 ≡ 491 mod 617

4: 408⁴=408²⁺²=408²⋅408² ≡ 491⋅491=241081 ≡ 451 mod 617

8: 408⁸=408⁴⁺⁴=408⁴⋅408⁴ ≡ 451⋅451=203401 ≡ 408 mod 617

16: 408¹⁶=408⁸⁺⁸=408⁸⋅408⁸ ≡ 408⋅408=166464 ≡ 491 mod 617

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

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

252 = 128+64+32+16+8+4

249²⁵²

= 249^{128+64+32+16+8+4}

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

≡ 231 ⋅ 256 ⋅ 337 ⋅ 168 ⋅ 232 ⋅ 244 mod 353
≡ 59136 ⋅ 337 ⋅ 168 ⋅ 232 ⋅ 244 mod 353 ≡ 185 ⋅ 337 ⋅ 168 ⋅ 232 ⋅ 244 mod 353
≡ 62345 ⋅ 168 ⋅ 232 ⋅ 244 mod 353 ≡ 217 ⋅ 168 ⋅ 232 ⋅ 244 mod 353
≡ 36456 ⋅ 232 ⋅ 244 mod 353 ≡ 97 ⋅ 232 ⋅ 244 mod 353
≡ 22504 ⋅ 244 mod 353 ≡ 265 ⋅ 244 mod 353
≡ 64660 mod 353 ≡ 61 mod 353

Es gilt also: 249²⁵² ≡ 61 mod 353

Berechnung des größten gemeinsamen Teilers von 97 und 58

=>97	= 1⋅58 + 39
=>58	= 1⋅39 + 19
=>39	= 2⋅19 + 1
=>19	= 19⋅1 + 0

also gilt: ggt(97,58)=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= 39-2⋅19
19= 58-1⋅39	eingesetzt in die Zeile drüber:	1	= 1⋅39 -2⋅(58 -1⋅ 39) = 1⋅39 -2⋅58 +2⋅ 39) = -2⋅58 +3⋅ 39 (=1)
39= 97-1⋅58	eingesetzt in die Zeile drüber:	1	= -2⋅58 +3⋅(97 -1⋅ 58) = -2⋅58 +3⋅97 -3⋅ 58) = 3⋅97 -5⋅ 58 (=1)

Es gilt also: ggt(97,58)=1 = 3⋅97 -5⋅58

oder wenn man 3⋅97 auf die linke Seite bringt:

1 -3⋅97 = -5⋅58

-5⋅58 = -3⋅97 + 1 |+97⋅58

-5⋅58 + 97⋅58 = -3⋅97 + 97⋅58 + 1

(-5 + 97) ⋅ 58 = (-3 + 58) ⋅ 97 + 1

92⋅58 = 55⋅97 + 1

Es gilt also: 92⋅58 = 55⋅97 +1

Somit 92⋅58 = 1 mod 97

92 ist also das Inverse von 58 mod 97