Um längere Rechnungen zu vermeiden, rechnen wir:

(88 - 3000) mod 3 ≡ (88 mod 3 - 3000 mod 3) mod 3.

88 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 88 = 90-2 = 3 ⋅ 30 -2 = 3 ⋅ 30 - 3 + 1.

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

Somit gilt:

(88 - 3000) mod 3 ≡ (1 - 0) mod 3 ≡ 1 mod 3.

Um längere Rechnungen zu vermeiden, rechnen wir:

(88 ⋅ 39) mod 4 ≡ (88 mod 4 ⋅ 39 mod 4) mod 4.

88 mod 4 ≡ 0 mod 4 kann man relativ leicht bestimmen, weil ja 88 = 88 + 0 = 22 ⋅ 4 + 0 ist.

39 mod 4 ≡ 3 mod 4 kann man relativ leicht bestimmen, weil ja 39 = 36 + 3 = 9 ⋅ 4 + 3 ist.

Somit gilt:

(88 ⋅ 39) mod 4 ≡ (0 ⋅ 3) mod 4 ≡ 0 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: 191¹=191

2: 191²=191¹⁺¹=191¹⋅191¹ ≡ 191⋅191=36481 ≡ 443 mod 487

4: 191⁴=191²⁺²=191²⋅191² ≡ 443⋅443=196249 ≡ 475 mod 487

8: 191⁸=191⁴⁺⁴=191⁴⋅191⁴ ≡ 475⋅475=225625 ≡ 144 mod 487

16: 191¹⁶=191⁸⁺⁸=191⁸⋅191⁸ ≡ 144⋅144=20736 ≡ 282 mod 487

32: 191³²=191¹⁶⁺¹⁶=191¹⁶⋅191¹⁶ ≡ 282⋅282=79524 ≡ 143 mod 487

64: 191⁶⁴=191³²⁺³²=191³²⋅191³² ≡ 143⋅143=20449 ≡ 482 mod 487

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

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

244 = 128+64+32+16+4

105²⁴⁴

= 105^{128+64+32+16+4}

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

≡ 293 ⋅ 194 ⋅ 116 ⋅ 151 ⋅ 207 mod 349
≡ 56842 ⋅ 116 ⋅ 151 ⋅ 207 mod 349 ≡ 304 ⋅ 116 ⋅ 151 ⋅ 207 mod 349
≡ 35264 ⋅ 151 ⋅ 207 mod 349 ≡ 15 ⋅ 151 ⋅ 207 mod 349
≡ 2265 ⋅ 207 mod 349 ≡ 171 ⋅ 207 mod 349
≡ 35397 mod 349 ≡ 148 mod 349

Es gilt also: 105²⁴⁴ ≡ 148 mod 349

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

=>89	= 2⋅35 + 19
=>35	= 1⋅19 + 16
=>19	= 1⋅16 + 3
=>16	= 5⋅3 + 1
=>3	= 3⋅1 + 0

also gilt: ggt(89,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= 16-5⋅3
3= 19-1⋅16	eingesetzt in die Zeile drüber:	1	= 1⋅16 -5⋅(19 -1⋅ 16) = 1⋅16 -5⋅19 +5⋅ 16) = -5⋅19 +6⋅ 16 (=1)
16= 35-1⋅19	eingesetzt in die Zeile drüber:	1	= -5⋅19 +6⋅(35 -1⋅ 19) = -5⋅19 +6⋅35 -6⋅ 19) = 6⋅35 -11⋅ 19 (=1)
19= 89-2⋅35	eingesetzt in die Zeile drüber:	1	= 6⋅35 -11⋅(89 -2⋅ 35) = 6⋅35 -11⋅89 +22⋅ 35) = -11⋅89 +28⋅ 35 (=1)

Es gilt also: ggt(89,35)=1 = -11⋅89 +28⋅35

oder wenn man -11⋅89 auf die linke Seite bringt:

1 +11⋅89 = +28⋅35

Es gilt also: 28⋅35 = 11⋅89 +1

Somit 28⋅35 = 1 mod 89

28 ist also das Inverse von 35 mod 89