Um längere Rechnungen zu vermeiden, rechnen wir:

(13998 + 136) mod 7 ≡ (13998 mod 7 + 136 mod 7) mod 7.

13998 mod 7 ≡ 5 mod 7 kann man relativ leicht bestimmen, weil ja 13998 = 14000-2 = 7 ⋅ 2000 -2 = 7 ⋅ 2000 - 7 + 5.

136 mod 7 ≡ 3 mod 7 kann man relativ leicht bestimmen, weil ja 136 = 140-4 = 7 ⋅ 20 -4 = 7 ⋅ 20 - 7 + 3.

Somit gilt:

(13998 + 136) mod 7 ≡ (5 + 3) mod 7 ≡ 8 mod 7 ≡ 1 mod 7.

Um längere Rechnungen zu vermeiden, rechnen wir:

(64 ⋅ 49) mod 3 ≡ (64 mod 3 ⋅ 49 mod 3) mod 3.

64 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 64 = 63 + 1 = 21 ⋅ 3 + 1 ist.

49 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 49 = 48 + 1 = 16 ⋅ 3 + 1 ist.

Somit gilt:

(64 ⋅ 49) mod 3 ≡ (1 ⋅ 1) mod 3 ≡ 1 mod 3.

Die 128 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: 170¹=170

2: 170²=170¹⁺¹=170¹⋅170¹ ≡ 170⋅170=28900 ≡ 103 mod 331

4: 170⁴=170²⁺²=170²⋅170² ≡ 103⋅103=10609 ≡ 17 mod 331

8: 170⁸=170⁴⁺⁴=170⁴⋅170⁴ ≡ 17⋅17=289 ≡ 289 mod 331

16: 170¹⁶=170⁸⁺⁸=170⁸⋅170⁸ ≡ 289⋅289=83521 ≡ 109 mod 331

32: 170³²=170¹⁶⁺¹⁶=170¹⁶⋅170¹⁶ ≡ 109⋅109=11881 ≡ 296 mod 331

64: 170⁶⁴=170³²⁺³²=170³²⋅170³² ≡ 296⋅296=87616 ≡ 232 mod 331

128: 170¹²⁸=170⁶⁴⁺⁶⁴=170⁶⁴⋅170⁶⁴ ≡ 232⋅232=53824 ≡ 202 mod 331

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

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

214 = 128+64+16+4+2

772²¹⁴

= 772^{128+64+16+4+2}

= 772¹²⁸⋅772⁶⁴⋅772¹⁶⋅772⁴⋅772²

≡ 174 ⋅ 796 ⋅ 511 ⋅ 118 ⋅ 514 mod 863
≡ 138504 ⋅ 511 ⋅ 118 ⋅ 514 mod 863 ≡ 424 ⋅ 511 ⋅ 118 ⋅ 514 mod 863
≡ 216664 ⋅ 118 ⋅ 514 mod 863 ≡ 51 ⋅ 118 ⋅ 514 mod 863
≡ 6018 ⋅ 514 mod 863 ≡ 840 ⋅ 514 mod 863
≡ 431760 mod 863 ≡ 260 mod 863

Es gilt also: 772²¹⁴ ≡ 260 mod 863

Berechnung des größten gemeinsamen Teilers von 89 und 27

=>89	= 3⋅27 + 8
=>27	= 3⋅8 + 3
=>8	= 2⋅3 + 2
=>3	= 1⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(89,27)=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= 3-1⋅2
2= 8-2⋅3	eingesetzt in die Zeile drüber:	1	= 1⋅3 -1⋅(8 -2⋅ 3) = 1⋅3 -1⋅8 +2⋅ 3) = -1⋅8 +3⋅ 3 (=1)
3= 27-3⋅8	eingesetzt in die Zeile drüber:	1	= -1⋅8 +3⋅(27 -3⋅ 8) = -1⋅8 +3⋅27 -9⋅ 8) = 3⋅27 -10⋅ 8 (=1)
8= 89-3⋅27	eingesetzt in die Zeile drüber:	1	= 3⋅27 -10⋅(89 -3⋅ 27) = 3⋅27 -10⋅89 +30⋅ 27) = -10⋅89 +33⋅ 27 (=1)

Es gilt also: ggt(89,27)=1 = -10⋅89 +33⋅27

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

1 +10⋅89 = +33⋅27

Es gilt also: 33⋅27 = 10⋅89 +1

Somit 33⋅27 = 1 mod 89

33 ist also das Inverse von 27 mod 89