Um längere Rechnungen zu vermeiden, rechnen wir:

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

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

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

Somit gilt:

(14998 + 15000) mod 3 ≡ (1 + 0) mod 3 ≡ 1 mod 3.

Um längere Rechnungen zu vermeiden, rechnen wir:

(39 ⋅ 25) mod 10 ≡ (39 mod 10 ⋅ 25 mod 10) mod 10.

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

25 mod 10 ≡ 5 mod 10 kann man relativ leicht bestimmen, weil ja 25 = 20 + 5 = 2 ⋅ 10 + 5 ist.

Somit gilt:

(39 ⋅ 25) mod 10 ≡ (9 ⋅ 5) mod 10 ≡ 45 mod 10 ≡ 5 mod 10.

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

2: 765²=765¹⁺¹=765¹⋅765¹ ≡ 765⋅765=585225 ≡ 673 mod 821

4: 765⁴=765²⁺²=765²⋅765² ≡ 673⋅673=452929 ≡ 558 mod 821

8: 765⁸=765⁴⁺⁴=765⁴⋅765⁴ ≡ 558⋅558=311364 ≡ 205 mod 821

16: 765¹⁶=765⁸⁺⁸=765⁸⋅765⁸ ≡ 205⋅205=42025 ≡ 154 mod 821

32: 765³²=765¹⁶⁺¹⁶=765¹⁶⋅765¹⁶ ≡ 154⋅154=23716 ≡ 728 mod 821

64: 765⁶⁴=765³²⁺³²=765³²⋅765³² ≡ 728⋅728=529984 ≡ 439 mod 821

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

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

115 = 64+32+16+2+1

684¹¹⁵

= 684^64+32+16+2+1

= 684⁶⁴⋅684³²⋅684¹⁶⋅684²⋅684¹

≡ 621 ⋅ 574 ⋅ 85 ⋅ 69 ⋅ 684 mod 739
≡ 356454 ⋅ 85 ⋅ 69 ⋅ 684 mod 739 ≡ 256 ⋅ 85 ⋅ 69 ⋅ 684 mod 739
≡ 21760 ⋅ 69 ⋅ 684 mod 739 ≡ 329 ⋅ 69 ⋅ 684 mod 739
≡ 22701 ⋅ 684 mod 739 ≡ 531 ⋅ 684 mod 739
≡ 363204 mod 739 ≡ 355 mod 739

Es gilt also: 684¹¹⁵ ≡ 355 mod 739

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

=>61	= 1⋅47 + 14
=>47	= 3⋅14 + 5
=>14	= 2⋅5 + 4
=>5	= 1⋅4 + 1
=>4	= 4⋅1 + 0

also gilt: ggt(61,47)=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= 5-1⋅4
4= 14-2⋅5	eingesetzt in die Zeile drüber:	1	= 1⋅5 -1⋅(14 -2⋅ 5) = 1⋅5 -1⋅14 +2⋅ 5) = -1⋅14 +3⋅ 5 (=1)
5= 47-3⋅14	eingesetzt in die Zeile drüber:	1	= -1⋅14 +3⋅(47 -3⋅ 14) = -1⋅14 +3⋅47 -9⋅ 14) = 3⋅47 -10⋅ 14 (=1)
14= 61-1⋅47	eingesetzt in die Zeile drüber:	1	= 3⋅47 -10⋅(61 -1⋅ 47) = 3⋅47 -10⋅61 +10⋅ 47) = -10⋅61 +13⋅ 47 (=1)

Es gilt also: ggt(61,47)=1 = -10⋅61 +13⋅47

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

1 +10⋅61 = +13⋅47

Es gilt also: 13⋅47 = 10⋅61 +1

Somit 13⋅47 = 1 mod 61

13 ist also das Inverse von 47 mod 61