Um längere Rechnungen zu vermeiden, rechnen wir:

(16001 + 7994) mod 8 ≡ (16001 mod 8 + 7994 mod 8) mod 8.

16001 mod 8 ≡ 1 mod 8 kann man relativ leicht bestimmen, weil ja 16001 = 16000+1 = 8 ⋅ 2000 +1.

7994 mod 8 ≡ 2 mod 8 kann man relativ leicht bestimmen, weil ja 7994 = 7000+994 = 8 ⋅ 875 +994.

Somit gilt:

(16001 + 7994) mod 8 ≡ (1 + 2) mod 8 ≡ 3 mod 8.

Um längere Rechnungen zu vermeiden, rechnen wir:

(43 ⋅ 48) mod 6 ≡ (43 mod 6 ⋅ 48 mod 6) mod 6.

43 mod 6 ≡ 1 mod 6 kann man relativ leicht bestimmen, weil ja 43 = 42 + 1 = 7 ⋅ 6 + 1 ist.

48 mod 6 ≡ 0 mod 6 kann man relativ leicht bestimmen, weil ja 48 = 48 + 0 = 8 ⋅ 6 + 0 ist.

Somit gilt:

(43 ⋅ 48) mod 6 ≡ (1 ⋅ 0) mod 6 ≡ 0 mod 6.

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

2: 545²=545¹⁺¹=545¹⋅545¹ ≡ 545⋅545=297025 ≡ 105 mod 571

4: 545⁴=545²⁺²=545²⋅545² ≡ 105⋅105=11025 ≡ 176 mod 571

8: 545⁸=545⁴⁺⁴=545⁴⋅545⁴ ≡ 176⋅176=30976 ≡ 142 mod 571

16: 545¹⁶=545⁸⁺⁸=545⁸⋅545⁸ ≡ 142⋅142=20164 ≡ 179 mod 571

32: 545³²=545¹⁶⁺¹⁶=545¹⁶⋅545¹⁶ ≡ 179⋅179=32041 ≡ 65 mod 571

64: 545⁶⁴=545³²⁺³²=545³²⋅545³² ≡ 65⋅65=4225 ≡ 228 mod 571

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

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

248 = 128+64+32+16+8

777²⁴⁸

= 777^{128+64+32+16+8}

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

≡ 553 ⋅ 879 ⋅ 702 ⋅ 146 ⋅ 488 mod 937
≡ 486087 ⋅ 702 ⋅ 146 ⋅ 488 mod 937 ≡ 721 ⋅ 702 ⋅ 146 ⋅ 488 mod 937
≡ 506142 ⋅ 146 ⋅ 488 mod 937 ≡ 162 ⋅ 146 ⋅ 488 mod 937
≡ 23652 ⋅ 488 mod 937 ≡ 227 ⋅ 488 mod 937
≡ 110776 mod 937 ≡ 210 mod 937

Es gilt also: 777²⁴⁸ ≡ 210 mod 937

Berechnung des größten gemeinsamen Teilers von 73 und 51

=>73	= 1⋅51 + 22
=>51	= 2⋅22 + 7
=>22	= 3⋅7 + 1
=>7	= 7⋅1 + 0

also gilt: ggt(73,51)=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= 22-3⋅7
7= 51-2⋅22	eingesetzt in die Zeile drüber:	1	= 1⋅22 -3⋅(51 -2⋅ 22) = 1⋅22 -3⋅51 +6⋅ 22) = -3⋅51 +7⋅ 22 (=1)
22= 73-1⋅51	eingesetzt in die Zeile drüber:	1	= -3⋅51 +7⋅(73 -1⋅ 51) = -3⋅51 +7⋅73 -7⋅ 51) = 7⋅73 -10⋅ 51 (=1)

Es gilt also: ggt(73,51)=1 = 7⋅73 -10⋅51

oder wenn man 7⋅73 auf die linke Seite bringt:

1 -7⋅73 = -10⋅51

-10⋅51 = -7⋅73 + 1 |+73⋅51

-10⋅51 + 73⋅51 = -7⋅73 + 73⋅51 + 1

(-10 + 73) ⋅ 51 = (-7 + 51) ⋅ 73 + 1

63⋅51 = 44⋅73 + 1

Es gilt also: 63⋅51 = 44⋅73 +1

Somit 63⋅51 = 1 mod 73

63 ist also das Inverse von 51 mod 73