Um längere Rechnungen zu vermeiden, rechnen wir:

(47 + 497) mod 5 ≡ (47 mod 5 + 497 mod 5) mod 5.

47 mod 5 ≡ 2 mod 5 kann man relativ leicht bestimmen, weil ja 47 = 40+7 = 5 ⋅ 8 +7.

497 mod 5 ≡ 2 mod 5 kann man relativ leicht bestimmen, weil ja 497 = 400+97 = 5 ⋅ 80 +97.

Somit gilt:

(47 + 497) mod 5 ≡ (2 + 2) mod 5 ≡ 4 mod 5.

Um längere Rechnungen zu vermeiden, rechnen wir:

(29 ⋅ 51) mod 5 ≡ (29 mod 5 ⋅ 51 mod 5) mod 5.

29 mod 5 ≡ 4 mod 5 kann man relativ leicht bestimmen, weil ja 29 = 25 + 4 = 5 ⋅ 5 + 4 ist.

51 mod 5 ≡ 1 mod 5 kann man relativ leicht bestimmen, weil ja 51 = 50 + 1 = 10 ⋅ 5 + 1 ist.

Somit gilt:

(29 ⋅ 51) mod 5 ≡ (4 ⋅ 1) mod 5 ≡ 4 mod 5.

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

2: 654²=654¹⁺¹=654¹⋅654¹ ≡ 654⋅654=427716 ≡ 524 mod 797

4: 654⁴=654²⁺²=654²⋅654² ≡ 524⋅524=274576 ≡ 408 mod 797

8: 654⁸=654⁴⁺⁴=654⁴⋅654⁴ ≡ 408⋅408=166464 ≡ 688 mod 797

16: 654¹⁶=654⁸⁺⁸=654⁸⋅654⁸ ≡ 688⋅688=473344 ≡ 723 mod 797

32: 654³²=654¹⁶⁺¹⁶=654¹⁶⋅654¹⁶ ≡ 723⋅723=522729 ≡ 694 mod 797

64: 654⁶⁴=654³²⁺³²=654³²⋅654³² ≡ 694⋅694=481636 ≡ 248 mod 797

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

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

241 = 128+64+32+16+1

209²⁴¹

= 209^{128+64+32+16+1}

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

≡ 135 ⋅ 64 ⋅ 8 ⋅ 63 ⋅ 209 mod 233
≡ 8640 ⋅ 8 ⋅ 63 ⋅ 209 mod 233 ≡ 19 ⋅ 8 ⋅ 63 ⋅ 209 mod 233
≡ 152 ⋅ 63 ⋅ 209 mod 233
≡ 9576 ⋅ 209 mod 233 ≡ 23 ⋅ 209 mod 233
≡ 4807 mod 233 ≡ 147 mod 233

Es gilt also: 209²⁴¹ ≡ 147 mod 233

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