Um längere Rechnungen zu vermeiden, rechnen wir:

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

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

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

Somit gilt:

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

Um längere Rechnungen zu vermeiden, rechnen wir:

(54 ⋅ 55) mod 4 ≡ (54 mod 4 ⋅ 55 mod 4) mod 4.

54 mod 4 ≡ 2 mod 4 kann man relativ leicht bestimmen, weil ja 54 = 52 + 2 = 13 ⋅ 4 + 2 ist.

55 mod 4 ≡ 3 mod 4 kann man relativ leicht bestimmen, weil ja 55 = 52 + 3 = 13 ⋅ 4 + 3 ist.

Somit gilt:

(54 ⋅ 55) mod 4 ≡ (2 ⋅ 3) mod 4 ≡ 6 mod 4 ≡ 2 mod 4.

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

2: 651²=651¹⁺¹=651¹⋅651¹ ≡ 651⋅651=423801 ≡ 377 mod 827

4: 651⁴=651²⁺²=651²⋅651² ≡ 377⋅377=142129 ≡ 712 mod 827

8: 651⁸=651⁴⁺⁴=651⁴⋅651⁴ ≡ 712⋅712=506944 ≡ 820 mod 827

16: 651¹⁶=651⁸⁺⁸=651⁸⋅651⁸ ≡ 820⋅820=672400 ≡ 49 mod 827

32: 651³²=651¹⁶⁺¹⁶=651¹⁶⋅651¹⁶ ≡ 49⋅49=2401 ≡ 747 mod 827

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

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

124 = 64+32+16+8+4

291¹²⁴

= 291^64+32+16+8+4

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

≡ 447 ⋅ 395 ⋅ 43 ⋅ 267 ⋅ 392 mod 727
≡ 176565 ⋅ 43 ⋅ 267 ⋅ 392 mod 727 ≡ 631 ⋅ 43 ⋅ 267 ⋅ 392 mod 727
≡ 27133 ⋅ 267 ⋅ 392 mod 727 ≡ 234 ⋅ 267 ⋅ 392 mod 727
≡ 62478 ⋅ 392 mod 727 ≡ 683 ⋅ 392 mod 727
≡ 267736 mod 727 ≡ 200 mod 727

Es gilt also: 291¹²⁴ ≡ 200 mod 727

Berechnung des größten gemeinsamen Teilers von 101 und 55

=>101	= 1⋅55 + 46
=>55	= 1⋅46 + 9
=>46	= 5⋅9 + 1
=>9	= 9⋅1 + 0

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

Es gilt also: ggt(101,55)=1 = 6⋅101 -11⋅55

oder wenn man 6⋅101 auf die linke Seite bringt:

1 -6⋅101 = -11⋅55

-11⋅55 = -6⋅101 + 1 |+101⋅55

-11⋅55 + 101⋅55 = -6⋅101 + 101⋅55 + 1

(-11 + 101) ⋅ 55 = (-6 + 55) ⋅ 101 + 1

90⋅55 = 49⋅101 + 1

Es gilt also: 90⋅55 = 49⋅101 +1

Somit 90⋅55 = 1 mod 101

90 ist also das Inverse von 55 mod 101