Um längere Rechnungen zu vermeiden, rechnen wir:

(15996 - 164) mod 4 ≡ (15996 mod 4 - 164 mod 4) mod 4.

15996 mod 4 ≡ 0 mod 4 kann man relativ leicht bestimmen, weil ja 15996 = 15000+996 = 4 ⋅ 3750 +996.

164 mod 4 ≡ 0 mod 4 kann man relativ leicht bestimmen, weil ja 164 = 160+4 = 4 ⋅ 40 +4.

Somit gilt:

(15996 - 164) mod 4 ≡ (0 - 0) mod 4 ≡ 0 mod 4.

Um längere Rechnungen zu vermeiden, rechnen wir:

(48 ⋅ 25) mod 7 ≡ (48 mod 7 ⋅ 25 mod 7) mod 7.

48 mod 7 ≡ 6 mod 7 kann man relativ leicht bestimmen, weil ja 48 = 42 + 6 = 6 ⋅ 7 + 6 ist.

25 mod 7 ≡ 4 mod 7 kann man relativ leicht bestimmen, weil ja 25 = 21 + 4 = 3 ⋅ 7 + 4 ist.

Somit gilt:

(48 ⋅ 25) mod 7 ≡ (6 ⋅ 4) mod 7 ≡ 24 mod 7 ≡ 3 mod 7.

Die 8 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: 556¹=556

2: 556²=556¹⁺¹=556¹⋅556¹ ≡ 556⋅556=309136 ≡ 170 mod 761

4: 556⁴=556²⁺²=556²⋅556² ≡ 170⋅170=28900 ≡ 743 mod 761

8: 556⁸=556⁴⁺⁴=556⁴⋅556⁴ ≡ 743⋅743=552049 ≡ 324 mod 761

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

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

249 = 128+64+32+16+8+1

386²⁴⁹

= 386^{128+64+32+16+8+1}

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

≡ 363 ⋅ 615 ⋅ 722 ⋅ 290 ⋅ 340 ⋅ 386 mod 887
≡ 223245 ⋅ 722 ⋅ 290 ⋅ 340 ⋅ 386 mod 887 ≡ 608 ⋅ 722 ⋅ 290 ⋅ 340 ⋅ 386 mod 887
≡ 438976 ⋅ 290 ⋅ 340 ⋅ 386 mod 887 ≡ 798 ⋅ 290 ⋅ 340 ⋅ 386 mod 887
≡ 231420 ⋅ 340 ⋅ 386 mod 887 ≡ 800 ⋅ 340 ⋅ 386 mod 887
≡ 272000 ⋅ 386 mod 887 ≡ 578 ⋅ 386 mod 887
≡ 223108 mod 887 ≡ 471 mod 887

Es gilt also: 386²⁴⁹ ≡ 471 mod 887

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

=>83	= 1⋅46 + 37
=>46	= 1⋅37 + 9
=>37	= 4⋅9 + 1
=>9	= 9⋅1 + 0

also gilt: ggt(83,46)=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= 37-4⋅9
9= 46-1⋅37	eingesetzt in die Zeile drüber:	1	= 1⋅37 -4⋅(46 -1⋅ 37) = 1⋅37 -4⋅46 +4⋅ 37) = -4⋅46 +5⋅ 37 (=1)
37= 83-1⋅46	eingesetzt in die Zeile drüber:	1	= -4⋅46 +5⋅(83 -1⋅ 46) = -4⋅46 +5⋅83 -5⋅ 46) = 5⋅83 -9⋅ 46 (=1)

Es gilt also: ggt(83,46)=1 = 5⋅83 -9⋅46

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

1 -5⋅83 = -9⋅46

-9⋅46 = -5⋅83 + 1 |+83⋅46

-9⋅46 + 83⋅46 = -5⋅83 + 83⋅46 + 1

(-9 + 83) ⋅ 46 = (-5 + 46) ⋅ 83 + 1

74⋅46 = 41⋅83 + 1

Es gilt also: 74⋅46 = 41⋅83 +1

Somit 74⋅46 = 1 mod 83

74 ist also das Inverse von 46 mod 83