Um längere Rechnungen zu vermeiden, rechnen wir:

(57 + 147) mod 3 ≡ (57 mod 3 + 147 mod 3) mod 3.

57 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 57 = 60-3 = 3 ⋅ 20 -3 = 3 ⋅ 20 - 3 + 0.

147 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 147 = 150-3 = 3 ⋅ 50 -3 = 3 ⋅ 50 - 3 + 0.

Somit gilt:

(57 + 147) mod 3 ≡ (0 + 0) mod 3 ≡ 0 mod 3.

Um längere Rechnungen zu vermeiden, rechnen wir:

(44 ⋅ 40) mod 9 ≡ (44 mod 9 ⋅ 40 mod 9) mod 9.

44 mod 9 ≡ 8 mod 9 kann man relativ leicht bestimmen, weil ja 44 = 36 + 8 = 4 ⋅ 9 + 8 ist.

40 mod 9 ≡ 4 mod 9 kann man relativ leicht bestimmen, weil ja 40 = 36 + 4 = 4 ⋅ 9 + 4 ist.

Somit gilt:

(44 ⋅ 40) mod 9 ≡ (8 ⋅ 4) mod 9 ≡ 32 mod 9 ≡ 5 mod 9.

Die 32 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: 671¹=671

2: 671²=671¹⁺¹=671¹⋅671¹ ≡ 671⋅671=450241 ≡ 850 mod 919

4: 671⁴=671²⁺²=671²⋅671² ≡ 850⋅850=722500 ≡ 166 mod 919

8: 671⁸=671⁴⁺⁴=671⁴⋅671⁴ ≡ 166⋅166=27556 ≡ 905 mod 919

16: 671¹⁶=671⁸⁺⁸=671⁸⋅671⁸ ≡ 905⋅905=819025 ≡ 196 mod 919

32: 671³²=671¹⁶⁺¹⁶=671¹⁶⋅671¹⁶ ≡ 196⋅196=38416 ≡ 737 mod 919

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

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

252 = 128+64+32+16+8+4

350²⁵²

= 350^{128+64+32+16+8+4}

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

≡ 359 ⋅ 371 ⋅ 782 ⋅ 657 ⋅ 90 ⋅ 65 mod 827
≡ 133189 ⋅ 782 ⋅ 657 ⋅ 90 ⋅ 65 mod 827 ≡ 42 ⋅ 782 ⋅ 657 ⋅ 90 ⋅ 65 mod 827
≡ 32844 ⋅ 657 ⋅ 90 ⋅ 65 mod 827 ≡ 591 ⋅ 657 ⋅ 90 ⋅ 65 mod 827
≡ 388287 ⋅ 90 ⋅ 65 mod 827 ≡ 424 ⋅ 90 ⋅ 65 mod 827
≡ 38160 ⋅ 65 mod 827 ≡ 118 ⋅ 65 mod 827
≡ 7670 mod 827 ≡ 227 mod 827

Es gilt also: 350²⁵² ≡ 227 mod 827

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