Um längere Rechnungen zu vermeiden, rechnen wir:

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

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

188 mod 9 ≡ 8 mod 9 kann man relativ leicht bestimmen, weil ja 188 = 180+8 = 9 ⋅ 20 +8.

Somit gilt:

(27000 + 188) mod 9 ≡ (0 + 8) mod 9 ≡ 8 mod 9.

Um längere Rechnungen zu vermeiden, rechnen wir:

(23 ⋅ 58) mod 5 ≡ (23 mod 5 ⋅ 58 mod 5) mod 5.

23 mod 5 ≡ 3 mod 5 kann man relativ leicht bestimmen, weil ja 23 = 20 + 3 = 4 ⋅ 5 + 3 ist.

58 mod 5 ≡ 3 mod 5 kann man relativ leicht bestimmen, weil ja 58 = 55 + 3 = 11 ⋅ 5 + 3 ist.

Somit gilt:

(23 ⋅ 58) mod 5 ≡ (3 ⋅ 3) mod 5 ≡ 9 mod 5 ≡ 4 mod 5.

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

2: 291²=291¹⁺¹=291¹⋅291¹ ≡ 291⋅291=84681 ≡ 571 mod 647

4: 291⁴=291²⁺²=291²⋅291² ≡ 571⋅571=326041 ≡ 600 mod 647

8: 291⁸=291⁴⁺⁴=291⁴⋅291⁴ ≡ 600⋅600=360000 ≡ 268 mod 647

16: 291¹⁶=291⁸⁺⁸=291⁸⋅291⁸ ≡ 268⋅268=71824 ≡ 7 mod 647

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

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

187 = 128+32+16+8+2+1

302¹⁸⁷

= 302^{128+32+16+8+2+1}

= 302¹²⁸⋅302³²⋅302¹⁶⋅302⁸⋅302²⋅302¹

≡ 140 ⋅ 441 ⋅ 21 ⋅ 491 ⋅ 452 ⋅ 302 mod 709
≡ 61740 ⋅ 21 ⋅ 491 ⋅ 452 ⋅ 302 mod 709 ≡ 57 ⋅ 21 ⋅ 491 ⋅ 452 ⋅ 302 mod 709
≡ 1197 ⋅ 491 ⋅ 452 ⋅ 302 mod 709 ≡ 488 ⋅ 491 ⋅ 452 ⋅ 302 mod 709
≡ 239608 ⋅ 452 ⋅ 302 mod 709 ≡ 675 ⋅ 452 ⋅ 302 mod 709
≡ 305100 ⋅ 302 mod 709 ≡ 230 ⋅ 302 mod 709
≡ 69460 mod 709 ≡ 687 mod 709

Es gilt also: 302¹⁸⁷ ≡ 687 mod 709

Berechnung des größten gemeinsamen Teilers von 101 und 41

=>101	= 2⋅41 + 19
=>41	= 2⋅19 + 3
=>19	= 6⋅3 + 1
=>3	= 3⋅1 + 0

also gilt: ggt(101,41)=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= 19-6⋅3
3= 41-2⋅19	eingesetzt in die Zeile drüber:	1	= 1⋅19 -6⋅(41 -2⋅ 19) = 1⋅19 -6⋅41 +12⋅ 19) = -6⋅41 +13⋅ 19 (=1)
19= 101-2⋅41	eingesetzt in die Zeile drüber:	1	= -6⋅41 +13⋅(101 -2⋅ 41) = -6⋅41 +13⋅101 -26⋅ 41) = 13⋅101 -32⋅ 41 (=1)

Es gilt also: ggt(101,41)=1 = 13⋅101 -32⋅41

oder wenn man 13⋅101 auf die linke Seite bringt:

1 -13⋅101 = -32⋅41

-32⋅41 = -13⋅101 + 1 |+101⋅41

-32⋅41 + 101⋅41 = -13⋅101 + 101⋅41 + 1

(-32 + 101) ⋅ 41 = (-13 + 41) ⋅ 101 + 1

69⋅41 = 28⋅101 + 1

Es gilt also: 69⋅41 = 28⋅101 +1

Somit 69⋅41 = 1 mod 101

69 ist also das Inverse von 41 mod 101