Um längere Rechnungen zu vermeiden, rechnen wir:

(5001 - 19996) mod 5 ≡ (5001 mod 5 - 19996 mod 5) mod 5.

5001 mod 5 ≡ 1 mod 5 kann man relativ leicht bestimmen, weil ja 5001 = 5000+1 = 5 ⋅ 1000 +1.

19996 mod 5 ≡ 1 mod 5 kann man relativ leicht bestimmen, weil ja 19996 = 19000+996 = 5 ⋅ 3800 +996.

Somit gilt:

(5001 - 19996) mod 5 ≡ (1 - 1) mod 5 ≡ 0 mod 5.

Um längere Rechnungen zu vermeiden, rechnen wir:

(45 ⋅ 98) mod 11 ≡ (45 mod 11 ⋅ 98 mod 11) mod 11.

45 mod 11 ≡ 1 mod 11 kann man relativ leicht bestimmen, weil ja 45 = 44 + 1 = 4 ⋅ 11 + 1 ist.

98 mod 11 ≡ 10 mod 11 kann man relativ leicht bestimmen, weil ja 98 = 88 + 10 = 8 ⋅ 11 + 10 ist.

Somit gilt:

(45 ⋅ 98) mod 11 ≡ (1 ⋅ 10) mod 11 ≡ 10 mod 11.

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

2: 335²=335¹⁺¹=335¹⋅335¹ ≡ 335⋅335=112225 ≡ 215 mod 487

4: 335⁴=335²⁺²=335²⋅335² ≡ 215⋅215=46225 ≡ 447 mod 487

8: 335⁸=335⁴⁺⁴=335⁴⋅335⁴ ≡ 447⋅447=199809 ≡ 139 mod 487

16: 335¹⁶=335⁸⁺⁸=335⁸⋅335⁸ ≡ 139⋅139=19321 ≡ 328 mod 487

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

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

245 = 128+64+32+16+4+1

581²⁴⁵

= 581^{128+64+32+16+4+1}

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

≡ 555 ⋅ 420 ⋅ 142 ⋅ 555 ⋅ 142 ⋅ 581 mod 617
≡ 233100 ⋅ 142 ⋅ 555 ⋅ 142 ⋅ 581 mod 617 ≡ 491 ⋅ 142 ⋅ 555 ⋅ 142 ⋅ 581 mod 617
≡ 69722 ⋅ 555 ⋅ 142 ⋅ 581 mod 617 ≡ 1 ⋅ 555 ⋅ 142 ⋅ 581 mod 617
≡ 555 ⋅ 142 ⋅ 581 mod 617
≡ 78810 ⋅ 581 mod 617 ≡ 451 ⋅ 581 mod 617
≡ 262031 mod 617 ≡ 423 mod 617

Es gilt also: 581²⁴⁵ ≡ 423 mod 617

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

=>97	= 2⋅45 + 7
=>45	= 6⋅7 + 3
=>7	= 2⋅3 + 1
=>3	= 3⋅1 + 0

also gilt: ggt(97,45)=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= 7-2⋅3
3= 45-6⋅7	eingesetzt in die Zeile drüber:	1	= 1⋅7 -2⋅(45 -6⋅ 7) = 1⋅7 -2⋅45 +12⋅ 7) = -2⋅45 +13⋅ 7 (=1)
7= 97-2⋅45	eingesetzt in die Zeile drüber:	1	= -2⋅45 +13⋅(97 -2⋅ 45) = -2⋅45 +13⋅97 -26⋅ 45) = 13⋅97 -28⋅ 45 (=1)

Es gilt also: ggt(97,45)=1 = 13⋅97 -28⋅45

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

1 -13⋅97 = -28⋅45

-28⋅45 = -13⋅97 + 1 |+97⋅45

-28⋅45 + 97⋅45 = -13⋅97 + 97⋅45 + 1

(-28 + 97) ⋅ 45 = (-13 + 45) ⋅ 97 + 1

69⋅45 = 32⋅97 + 1

Es gilt also: 69⋅45 = 32⋅97 +1

Somit 69⋅45 = 1 mod 97

69 ist also das Inverse von 45 mod 97