Um längere Rechnungen zu vermeiden, rechnen wir:

(96 - 202) mod 5 ≡ (96 mod 5 - 202 mod 5) mod 5.

96 mod 5 ≡ 1 mod 5 kann man relativ leicht bestimmen, weil ja 96 = 90+6 = 5 ⋅ 18 +6.

202 mod 5 ≡ 2 mod 5 kann man relativ leicht bestimmen, weil ja 202 = 200+2 = 5 ⋅ 40 +2.

Somit gilt:

(96 - 202) mod 5 ≡ (1 - 2) mod 5 ≡ -1 mod 5 ≡ 4 mod 5.

Um längere Rechnungen zu vermeiden, rechnen wir:

(15 ⋅ 23) mod 11 ≡ (15 mod 11 ⋅ 23 mod 11) mod 11.

15 mod 11 ≡ 4 mod 11 kann man relativ leicht bestimmen, weil ja 15 = 11 + 4 = 1 ⋅ 11 + 4 ist.

23 mod 11 ≡ 1 mod 11 kann man relativ leicht bestimmen, weil ja 23 = 22 + 1 = 2 ⋅ 11 + 1 ist.

Somit gilt:

(15 ⋅ 23) mod 11 ≡ (4 ⋅ 1) mod 11 ≡ 4 mod 11.

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

2: 195²=195¹⁺¹=195¹⋅195¹ ≡ 195⋅195=38025 ≡ 388 mod 617

4: 195⁴=195²⁺²=195²⋅195² ≡ 388⋅388=150544 ≡ 613 mod 617

8: 195⁸=195⁴⁺⁴=195⁴⋅195⁴ ≡ 613⋅613=375769 ≡ 16 mod 617

16: 195¹⁶=195⁸⁺⁸=195⁸⋅195⁸ ≡ 16⋅16=256 ≡ 256 mod 617

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

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

191 = 128+32+16+8+4+2+1

352¹⁹¹

= 352^{128+32+16+8+4+2+1}

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

≡ 294 ⋅ 335 ⋅ 65 ⋅ 125 ⋅ 348 ⋅ 202 ⋅ 352 mod 389
≡ 98490 ⋅ 65 ⋅ 125 ⋅ 348 ⋅ 202 ⋅ 352 mod 389 ≡ 73 ⋅ 65 ⋅ 125 ⋅ 348 ⋅ 202 ⋅ 352 mod 389
≡ 4745 ⋅ 125 ⋅ 348 ⋅ 202 ⋅ 352 mod 389 ≡ 77 ⋅ 125 ⋅ 348 ⋅ 202 ⋅ 352 mod 389
≡ 9625 ⋅ 348 ⋅ 202 ⋅ 352 mod 389 ≡ 289 ⋅ 348 ⋅ 202 ⋅ 352 mod 389
≡ 100572 ⋅ 202 ⋅ 352 mod 389 ≡ 210 ⋅ 202 ⋅ 352 mod 389
≡ 42420 ⋅ 352 mod 389 ≡ 19 ⋅ 352 mod 389
≡ 6688 mod 389 ≡ 75 mod 389

Es gilt also: 352¹⁹¹ ≡ 75 mod 389

Berechnung des größten gemeinsamen Teilers von 61 und 18

=>61	= 3⋅18 + 7
=>18	= 2⋅7 + 4
=>7	= 1⋅4 + 3
=>4	= 1⋅3 + 1
=>3	= 3⋅1 + 0

also gilt: ggt(61,18)=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= 4-1⋅3
3= 7-1⋅4	eingesetzt in die Zeile drüber:	1	= 1⋅4 -1⋅(7 -1⋅ 4) = 1⋅4 -1⋅7 +1⋅ 4) = -1⋅7 +2⋅ 4 (=1)
4= 18-2⋅7	eingesetzt in die Zeile drüber:	1	= -1⋅7 +2⋅(18 -2⋅ 7) = -1⋅7 +2⋅18 -4⋅ 7) = 2⋅18 -5⋅ 7 (=1)
7= 61-3⋅18	eingesetzt in die Zeile drüber:	1	= 2⋅18 -5⋅(61 -3⋅ 18) = 2⋅18 -5⋅61 +15⋅ 18) = -5⋅61 +17⋅ 18 (=1)

Es gilt also: ggt(61,18)=1 = -5⋅61 +17⋅18

oder wenn man -5⋅61 auf die linke Seite bringt:

1 +5⋅61 = +17⋅18

Es gilt also: 17⋅18 = 5⋅61 +1

Somit 17⋅18 = 1 mod 61

17 ist also das Inverse von 18 mod 61