Um längere Rechnungen zu vermeiden, rechnen wir:

(1498 + 14998) mod 3 ≡ (1498 mod 3 + 14998 mod 3) mod 3.

1498 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 1498 = 1500-2 = 3 ⋅ 500 -2 = 3 ⋅ 500 - 3 + 1.

14998 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 14998 = 15000-2 = 3 ⋅ 5000 -2 = 3 ⋅ 5000 - 3 + 1.

Somit gilt:

(1498 + 14998) mod 3 ≡ (1 + 1) mod 3 ≡ 2 mod 3.

Um längere Rechnungen zu vermeiden, rechnen wir:

(47 ⋅ 63) mod 11 ≡ (47 mod 11 ⋅ 63 mod 11) mod 11.

47 mod 11 ≡ 3 mod 11 kann man relativ leicht bestimmen, weil ja 47 = 44 + 3 = 4 ⋅ 11 + 3 ist.

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

Somit gilt:

(47 ⋅ 63) mod 11 ≡ (3 ⋅ 8) mod 11 ≡ 24 mod 11 ≡ 2 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: 386¹=386

2: 386²=386¹⁺¹=386¹⋅386¹ ≡ 386⋅386=148996 ≡ 673 mod 1009

4: 386⁴=386²⁺²=386²⋅386² ≡ 673⋅673=452929 ≡ 897 mod 1009

8: 386⁸=386⁴⁺⁴=386⁴⋅386⁴ ≡ 897⋅897=804609 ≡ 436 mod 1009

16: 386¹⁶=386⁸⁺⁸=386⁸⋅386⁸ ≡ 436⋅436=190096 ≡ 404 mod 1009

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

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

95 = 64+16+8+4+2+1

798⁹⁵

= 798^{64+16+8+4+2+1}

= 798⁶⁴⋅798¹⁶⋅798⁸⋅798⁴⋅798²⋅798¹

≡ 8 ⋅ 744 ⋅ 520 ⋅ 225 ⋅ 15 ⋅ 798 mod 911
≡ 5952 ⋅ 520 ⋅ 225 ⋅ 15 ⋅ 798 mod 911 ≡ 486 ⋅ 520 ⋅ 225 ⋅ 15 ⋅ 798 mod 911
≡ 252720 ⋅ 225 ⋅ 15 ⋅ 798 mod 911 ≡ 373 ⋅ 225 ⋅ 15 ⋅ 798 mod 911
≡ 83925 ⋅ 15 ⋅ 798 mod 911 ≡ 113 ⋅ 15 ⋅ 798 mod 911
≡ 1695 ⋅ 798 mod 911 ≡ 784 ⋅ 798 mod 911
≡ 625632 mod 911 ≡ 686 mod 911

Es gilt also: 798⁹⁵ ≡ 686 mod 911

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