Um längere Rechnungen zu vermeiden, rechnen wir:

(59 + 60) mod 3 ≡ (59 mod 3 + 60 mod 3) mod 3.

59 mod 3 ≡ 2 mod 3 kann man relativ leicht bestimmen, weil ja 59 = 60-1 = 3 ⋅ 20 -1 = 3 ⋅ 20 - 3 + 2.

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

Somit gilt:

(59 + 60) mod 3 ≡ (2 + 0) mod 3 ≡ 2 mod 3.

Um längere Rechnungen zu vermeiden, rechnen wir:

(37 ⋅ 73) mod 5 ≡ (37 mod 5 ⋅ 73 mod 5) mod 5.

37 mod 5 ≡ 2 mod 5 kann man relativ leicht bestimmen, weil ja 37 = 35 + 2 = 7 ⋅ 5 + 2 ist.

73 mod 5 ≡ 3 mod 5 kann man relativ leicht bestimmen, weil ja 73 = 70 + 3 = 14 ⋅ 5 + 3 ist.

Somit gilt:

(37 ⋅ 73) mod 5 ≡ (2 ⋅ 3) mod 5 ≡ 6 mod 5 ≡ 1 mod 5.

Die 16 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 ≡ 42 mod 307

4: 170⁴=170²⁺²=170²⋅170² ≡ 42⋅42=1764 ≡ 229 mod 307

8: 170⁸=170⁴⁺⁴=170⁴⋅170⁴ ≡ 229⋅229=52441 ≡ 251 mod 307

16: 170¹⁶=170⁸⁺⁸=170⁸⋅170⁸ ≡ 251⋅251=63001 ≡ 66 mod 307

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

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

221 = 128+64+16+8+4+1

679²²¹

= 679^{128+64+16+8+4+1}

= 679¹²⁸⋅679⁶⁴⋅679¹⁶⋅679⁸⋅679⁴⋅679¹

≡ 729 ⋅ 27 ⋅ 290 ⋅ 732 ⋅ 425 ⋅ 679 mod 829
≡ 19683 ⋅ 290 ⋅ 732 ⋅ 425 ⋅ 679 mod 829 ≡ 616 ⋅ 290 ⋅ 732 ⋅ 425 ⋅ 679 mod 829
≡ 178640 ⋅ 732 ⋅ 425 ⋅ 679 mod 829 ≡ 405 ⋅ 732 ⋅ 425 ⋅ 679 mod 829
≡ 296460 ⋅ 425 ⋅ 679 mod 829 ≡ 507 ⋅ 425 ⋅ 679 mod 829
≡ 215475 ⋅ 679 mod 829 ≡ 764 ⋅ 679 mod 829
≡ 518756 mod 829 ≡ 631 mod 829

Es gilt also: 679²²¹ ≡ 631 mod 829

Berechnung des größten gemeinsamen Teilers von 61 und 22

=>61	= 2⋅22 + 17
=>22	= 1⋅17 + 5
=>17	= 3⋅5 + 2
=>5	= 2⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(61,22)=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= 5-2⋅2
2= 17-3⋅5	eingesetzt in die Zeile drüber:	1	= 1⋅5 -2⋅(17 -3⋅ 5) = 1⋅5 -2⋅17 +6⋅ 5) = -2⋅17 +7⋅ 5 (=1)
5= 22-1⋅17	eingesetzt in die Zeile drüber:	1	= -2⋅17 +7⋅(22 -1⋅ 17) = -2⋅17 +7⋅22 -7⋅ 17) = 7⋅22 -9⋅ 17 (=1)
17= 61-2⋅22	eingesetzt in die Zeile drüber:	1	= 7⋅22 -9⋅(61 -2⋅ 22) = 7⋅22 -9⋅61 +18⋅ 22) = -9⋅61 +25⋅ 22 (=1)

Es gilt also: ggt(61,22)=1 = -9⋅61 +25⋅22

oder wenn man -9⋅61 auf die linke Seite bringt:

1 +9⋅61 = +25⋅22

Es gilt also: 25⋅22 = 9⋅61 +1

Somit 25⋅22 = 1 mod 61

25 ist also das Inverse von 22 mod 61