Um längere Rechnungen zu vermeiden, rechnen wir:

(13996 + 2800) mod 7 ≡ (13996 mod 7 + 2800 mod 7) mod 7.

13996 mod 7 ≡ 3 mod 7 kann man relativ leicht bestimmen, weil ja 13996 = 14000-4 = 7 ⋅ 2000 -4 = 7 ⋅ 2000 - 7 + 3.

2800 mod 7 ≡ 0 mod 7 kann man relativ leicht bestimmen, weil ja 2800 = 2800+0 = 7 ⋅ 400 +0.

Somit gilt:

(13996 + 2800) mod 7 ≡ (3 + 0) mod 7 ≡ 3 mod 7.

Um längere Rechnungen zu vermeiden, rechnen wir:

(74 ⋅ 65) mod 9 ≡ (74 mod 9 ⋅ 65 mod 9) mod 9.

74 mod 9 ≡ 2 mod 9 kann man relativ leicht bestimmen, weil ja 74 = 72 + 2 = 8 ⋅ 9 + 2 ist.

65 mod 9 ≡ 2 mod 9 kann man relativ leicht bestimmen, weil ja 65 = 63 + 2 = 7 ⋅ 9 + 2 ist.

Somit gilt:

(74 ⋅ 65) mod 9 ≡ (2 ⋅ 2) mod 9 ≡ 4 mod 9.

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

2: 293²=293¹⁺¹=293¹⋅293¹ ≡ 293⋅293=85849 ≡ 780 mod 877

4: 293⁴=293²⁺²=293²⋅293² ≡ 780⋅780=608400 ≡ 639 mod 877

8: 293⁸=293⁴⁺⁴=293⁴⋅293⁴ ≡ 639⋅639=408321 ≡ 516 mod 877

16: 293¹⁶=293⁸⁺⁸=293⁸⋅293⁸ ≡ 516⋅516=266256 ≡ 525 mod 877

32: 293³²=293¹⁶⁺¹⁶=293¹⁶⋅293¹⁶ ≡ 525⋅525=275625 ≡ 247 mod 877

64: 293⁶⁴=293³²⁺³²=293³²⋅293³² ≡ 247⋅247=61009 ≡ 496 mod 877

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

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

109 = 64+32+8+4+1

238¹⁰⁹

= 238^64+32+8+4+1

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

≡ 335 ⋅ 256 ⋅ 481 ⋅ 372 ⋅ 238 mod 577
≡ 85760 ⋅ 481 ⋅ 372 ⋅ 238 mod 577 ≡ 364 ⋅ 481 ⋅ 372 ⋅ 238 mod 577
≡ 175084 ⋅ 372 ⋅ 238 mod 577 ≡ 253 ⋅ 372 ⋅ 238 mod 577
≡ 94116 ⋅ 238 mod 577 ≡ 65 ⋅ 238 mod 577
≡ 15470 mod 577 ≡ 468 mod 577

Es gilt also: 238¹⁰⁹ ≡ 468 mod 577

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

=>73	= 1⋅59 + 14
=>59	= 4⋅14 + 3
=>14	= 4⋅3 + 2
=>3	= 1⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(73,59)=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= 3-1⋅2
2= 14-4⋅3	eingesetzt in die Zeile drüber:	1	= 1⋅3 -1⋅(14 -4⋅ 3) = 1⋅3 -1⋅14 +4⋅ 3) = -1⋅14 +5⋅ 3 (=1)
3= 59-4⋅14	eingesetzt in die Zeile drüber:	1	= -1⋅14 +5⋅(59 -4⋅ 14) = -1⋅14 +5⋅59 -20⋅ 14) = 5⋅59 -21⋅ 14 (=1)
14= 73-1⋅59	eingesetzt in die Zeile drüber:	1	= 5⋅59 -21⋅(73 -1⋅ 59) = 5⋅59 -21⋅73 +21⋅ 59) = -21⋅73 +26⋅ 59 (=1)

Es gilt also: ggt(73,59)=1 = -21⋅73 +26⋅59

oder wenn man -21⋅73 auf die linke Seite bringt:

1 +21⋅73 = +26⋅59

Es gilt also: 26⋅59 = 21⋅73 +1

Somit 26⋅59 = 1 mod 73

26 ist also das Inverse von 59 mod 73