Um längere Rechnungen zu vermeiden, rechnen wir:

(216 + 69) mod 7 ≡ (216 mod 7 + 69 mod 7) mod 7.

216 mod 7 ≡ 6 mod 7 kann man relativ leicht bestimmen, weil ja 216 = 210+6 = 7 ⋅ 30 +6.

69 mod 7 ≡ 6 mod 7 kann man relativ leicht bestimmen, weil ja 69 = 70-1 = 7 ⋅ 10 -1 = 7 ⋅ 10 - 7 + 6.

Somit gilt:

(216 + 69) mod 7 ≡ (6 + 6) mod 7 ≡ 12 mod 7 ≡ 5 mod 7.

Um längere Rechnungen zu vermeiden, rechnen wir:

(19 ⋅ 23) mod 7 ≡ (19 mod 7 ⋅ 23 mod 7) mod 7.

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

23 mod 7 ≡ 2 mod 7 kann man relativ leicht bestimmen, weil ja 23 = 21 + 2 = 3 ⋅ 7 + 2 ist.

Somit gilt:

(19 ⋅ 23) mod 7 ≡ (5 ⋅ 2) mod 7 ≡ 10 mod 7 ≡ 3 mod 7.

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

2: 113²=113¹⁺¹=113¹⋅113¹ ≡ 113⋅113=12769 ≡ 102 mod 239

4: 113⁴=113²⁺²=113²⋅113² ≡ 102⋅102=10404 ≡ 127 mod 239

8: 113⁸=113⁴⁺⁴=113⁴⋅113⁴ ≡ 127⋅127=16129 ≡ 116 mod 239

16: 113¹⁶=113⁸⁺⁸=113⁸⋅113⁸ ≡ 116⋅116=13456 ≡ 72 mod 239

32: 113³²=113¹⁶⁺¹⁶=113¹⁶⋅113¹⁶ ≡ 72⋅72=5184 ≡ 165 mod 239

64: 113⁶⁴=113³²⁺³²=113³²⋅113³² ≡ 165⋅165=27225 ≡ 218 mod 239

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

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

79 = 64+8+4+2+1

617⁷⁹

= 617^64+8+4+2+1

= 617⁶⁴⋅617⁸⋅617⁴⋅617²⋅617¹

≡ 107 ⋅ 712 ⋅ 389 ⋅ 463 ⋅ 617 mod 823
≡ 76184 ⋅ 389 ⋅ 463 ⋅ 617 mod 823 ≡ 468 ⋅ 389 ⋅ 463 ⋅ 617 mod 823
≡ 182052 ⋅ 463 ⋅ 617 mod 823 ≡ 169 ⋅ 463 ⋅ 617 mod 823
≡ 78247 ⋅ 617 mod 823 ≡ 62 ⋅ 617 mod 823
≡ 38254 mod 823 ≡ 396 mod 823

Es gilt also: 617⁷⁹ ≡ 396 mod 823

Berechnung des größten gemeinsamen Teilers von 97 und 82

=>97	= 1⋅82 + 15
=>82	= 5⋅15 + 7
=>15	= 2⋅7 + 1
=>7	= 7⋅1 + 0

also gilt: ggt(97,82)=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= 15-2⋅7
7= 82-5⋅15	eingesetzt in die Zeile drüber:	1	= 1⋅15 -2⋅(82 -5⋅ 15) = 1⋅15 -2⋅82 +10⋅ 15) = -2⋅82 +11⋅ 15 (=1)
15= 97-1⋅82	eingesetzt in die Zeile drüber:	1	= -2⋅82 +11⋅(97 -1⋅ 82) = -2⋅82 +11⋅97 -11⋅ 82) = 11⋅97 -13⋅ 82 (=1)

Es gilt also: ggt(97,82)=1 = 11⋅97 -13⋅82

oder wenn man 11⋅97 auf die linke Seite bringt:

1 -11⋅97 = -13⋅82

-13⋅82 = -11⋅97 + 1 |+97⋅82

-13⋅82 + 97⋅82 = -11⋅97 + 97⋅82 + 1

(-13 + 97) ⋅ 82 = (-11 + 82) ⋅ 97 + 1

84⋅82 = 71⋅97 + 1

Es gilt also: 84⋅82 = 71⋅97 +1

Somit 84⋅82 = 1 mod 97

84 ist also das Inverse von 82 mod 97