Um längere Rechnungen zu vermeiden, rechnen wir:

(504 - 25004) mod 5 ≡ (504 mod 5 - 25004 mod 5) mod 5.

504 mod 5 ≡ 4 mod 5 kann man relativ leicht bestimmen, weil ja 504 = 500+4 = 5 ⋅ 100 +4.

25004 mod 5 ≡ 4 mod 5 kann man relativ leicht bestimmen, weil ja 25004 = 25000+4 = 5 ⋅ 5000 +4.

Somit gilt:

(504 - 25004) mod 5 ≡ (4 - 4) mod 5 ≡ 0 mod 5.

Um längere Rechnungen zu vermeiden, rechnen wir:

(96 ⋅ 46) mod 5 ≡ (96 mod 5 ⋅ 46 mod 5) mod 5.

96 mod 5 ≡ 1 mod 5 kann man relativ leicht bestimmen, weil ja 96 = 95 + 1 = 19 ⋅ 5 + 1 ist.

46 mod 5 ≡ 1 mod 5 kann man relativ leicht bestimmen, weil ja 46 = 45 + 1 = 9 ⋅ 5 + 1 ist.

Somit gilt:

(96 ⋅ 46) mod 5 ≡ (1 ⋅ 1) mod 5 ≡ 1 mod 5.

Die 32 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: 358¹=358

2: 358²=358¹⁺¹=358¹⋅358¹ ≡ 358⋅358=128164 ≡ 180 mod 421

4: 358⁴=358²⁺²=358²⋅358² ≡ 180⋅180=32400 ≡ 404 mod 421

8: 358⁸=358⁴⁺⁴=358⁴⋅358⁴ ≡ 404⋅404=163216 ≡ 289 mod 421

16: 358¹⁶=358⁸⁺⁸=358⁸⋅358⁸ ≡ 289⋅289=83521 ≡ 163 mod 421

32: 358³²=358¹⁶⁺¹⁶=358¹⁶⋅358¹⁶ ≡ 163⋅163=26569 ≡ 46 mod 421

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

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

244 = 128+64+32+16+4

215²⁴⁴

= 215^{128+64+32+16+4}

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

≡ 562 ⋅ 110 ⋅ 493 ⋅ 324 ⋅ 201 mod 641
≡ 61820 ⋅ 493 ⋅ 324 ⋅ 201 mod 641 ≡ 284 ⋅ 493 ⋅ 324 ⋅ 201 mod 641
≡ 140012 ⋅ 324 ⋅ 201 mod 641 ≡ 274 ⋅ 324 ⋅ 201 mod 641
≡ 88776 ⋅ 201 mod 641 ≡ 318 ⋅ 201 mod 641
≡ 63918 mod 641 ≡ 459 mod 641

Es gilt also: 215²⁴⁴ ≡ 459 mod 641

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

=>61	= 3⋅18 + 7
=>18	= 2⋅7 + 4
=>7	= 1⋅4 + 3
=>4	= 1⋅3 + 1
=>3	= 3⋅1 + 0

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

Es gilt also: ggt(61,18)=1 = -5⋅61 +17⋅18

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

1 +5⋅61 = +17⋅18

Es gilt also: 17⋅18 = 5⋅61 +1

Somit 17⋅18 = 1 mod 61

17 ist also das Inverse von 18 mod 61