Um längere Rechnungen zu vermeiden, rechnen wir:

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

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

2505 mod 5 ≡ 0 mod 5 kann man relativ leicht bestimmen, weil ja 2505 = 2500+5 = 5 ⋅ 500 +5.

Somit gilt:

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

Um längere Rechnungen zu vermeiden, rechnen wir:

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

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

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

Somit gilt:

(95 ⋅ 37) mod 5 ≡ (0 ⋅ 2) mod 5 ≡ 0 mod 5.

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

2: 436²=436¹⁺¹=436¹⋅436¹ ≡ 436⋅436=190096 ≡ 205 mod 541

4: 436⁴=436²⁺²=436²⋅436² ≡ 205⋅205=42025 ≡ 368 mod 541

8: 436⁸=436⁴⁺⁴=436⁴⋅436⁴ ≡ 368⋅368=135424 ≡ 174 mod 541

16: 436¹⁶=436⁸⁺⁸=436⁸⋅436⁸ ≡ 174⋅174=30276 ≡ 521 mod 541

32: 436³²=436¹⁶⁺¹⁶=436¹⁶⋅436¹⁶ ≡ 521⋅521=271441 ≡ 400 mod 541

64: 436⁶⁴=436³²⁺³²=436³²⋅436³² ≡ 400⋅400=160000 ≡ 405 mod 541

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

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

215 = 128+64+16+4+2+1

182²¹⁵

= 182^{128+64+16+4+2+1}

= 182¹²⁸⋅182⁶⁴⋅182¹⁶⋅182⁴⋅182²⋅182¹

≡ 175 ⋅ 117 ⋅ 128 ⋅ 46 ⋅ 38 ⋅ 182 mod 233
≡ 20475 ⋅ 128 ⋅ 46 ⋅ 38 ⋅ 182 mod 233 ≡ 204 ⋅ 128 ⋅ 46 ⋅ 38 ⋅ 182 mod 233
≡ 26112 ⋅ 46 ⋅ 38 ⋅ 182 mod 233 ≡ 16 ⋅ 46 ⋅ 38 ⋅ 182 mod 233
≡ 736 ⋅ 38 ⋅ 182 mod 233 ≡ 37 ⋅ 38 ⋅ 182 mod 233
≡ 1406 ⋅ 182 mod 233 ≡ 8 ⋅ 182 mod 233
≡ 1456 mod 233 ≡ 58 mod 233

Es gilt also: 182²¹⁵ ≡ 58 mod 233

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

=>61	= 1⋅35 + 26
=>35	= 1⋅26 + 9
=>26	= 2⋅9 + 8
=>9	= 1⋅8 + 1
=>8	= 8⋅1 + 0

also gilt: ggt(61,35)=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= 9-1⋅8
8= 26-2⋅9	eingesetzt in die Zeile drüber:	1	= 1⋅9 -1⋅(26 -2⋅ 9) = 1⋅9 -1⋅26 +2⋅ 9) = -1⋅26 +3⋅ 9 (=1)
9= 35-1⋅26	eingesetzt in die Zeile drüber:	1	= -1⋅26 +3⋅(35 -1⋅ 26) = -1⋅26 +3⋅35 -3⋅ 26) = 3⋅35 -4⋅ 26 (=1)
26= 61-1⋅35	eingesetzt in die Zeile drüber:	1	= 3⋅35 -4⋅(61 -1⋅ 35) = 3⋅35 -4⋅61 +4⋅ 35) = -4⋅61 +7⋅ 35 (=1)

Es gilt also: ggt(61,35)=1 = -4⋅61 +7⋅35

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

1 +4⋅61 = +7⋅35

Es gilt also: 7⋅35 = 4⋅61 +1

Somit 7⋅35 = 1 mod 61

7 ist also das Inverse von 35 mod 61