Um längere Rechnungen zu vermeiden, rechnen wir:

(1600 + 201) mod 4 ≡ (1600 mod 4 + 201 mod 4) mod 4.

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

201 mod 4 ≡ 1 mod 4 kann man relativ leicht bestimmen, weil ja 201 = 200+1 = 4 ⋅ 50 +1.

Somit gilt:

(1600 + 201) mod 4 ≡ (0 + 1) mod 4 ≡ 1 mod 4.

Um längere Rechnungen zu vermeiden, rechnen wir:

(35 ⋅ 64) mod 4 ≡ (35 mod 4 ⋅ 64 mod 4) mod 4.

35 mod 4 ≡ 3 mod 4 kann man relativ leicht bestimmen, weil ja 35 = 32 + 3 = 8 ⋅ 4 + 3 ist.

64 mod 4 ≡ 0 mod 4 kann man relativ leicht bestimmen, weil ja 64 = 64 + 0 = 16 ⋅ 4 + 0 ist.

Somit gilt:

(35 ⋅ 64) mod 4 ≡ (3 ⋅ 0) mod 4 ≡ 0 mod 4.

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

2: 267²=267¹⁺¹=267¹⋅267¹ ≡ 267⋅267=71289 ≡ 90 mod 293

4: 267⁴=267²⁺²=267²⋅267² ≡ 90⋅90=8100 ≡ 189 mod 293

8: 267⁸=267⁴⁺⁴=267⁴⋅267⁴ ≡ 189⋅189=35721 ≡ 268 mod 293

16: 267¹⁶=267⁸⁺⁸=267⁸⋅267⁸ ≡ 268⋅268=71824 ≡ 39 mod 293

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

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

254 = 128+64+32+16+8+4+2

456²⁵⁴

= 456^{128+64+32+16+8+4+2}

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

≡ 198 ⋅ 342 ⋅ 29 ⋅ 45 ⋅ 150 ⋅ 152 ⋅ 352 mod 499
≡ 67716 ⋅ 29 ⋅ 45 ⋅ 150 ⋅ 152 ⋅ 352 mod 499 ≡ 351 ⋅ 29 ⋅ 45 ⋅ 150 ⋅ 152 ⋅ 352 mod 499
≡ 10179 ⋅ 45 ⋅ 150 ⋅ 152 ⋅ 352 mod 499 ≡ 199 ⋅ 45 ⋅ 150 ⋅ 152 ⋅ 352 mod 499
≡ 8955 ⋅ 150 ⋅ 152 ⋅ 352 mod 499 ≡ 472 ⋅ 150 ⋅ 152 ⋅ 352 mod 499
≡ 70800 ⋅ 152 ⋅ 352 mod 499 ≡ 441 ⋅ 152 ⋅ 352 mod 499
≡ 67032 ⋅ 352 mod 499 ≡ 166 ⋅ 352 mod 499
≡ 58432 mod 499 ≡ 49 mod 499

Es gilt also: 456²⁵⁴ ≡ 49 mod 499

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

=>59	= 1⋅52 + 7
=>52	= 7⋅7 + 3
=>7	= 2⋅3 + 1
=>3	= 3⋅1 + 0

also gilt: ggt(59,52)=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= 52-7⋅7	eingesetzt in die Zeile drüber:	1	= 1⋅7 -2⋅(52 -7⋅ 7) = 1⋅7 -2⋅52 +14⋅ 7) = -2⋅52 +15⋅ 7 (=1)
7= 59-1⋅52	eingesetzt in die Zeile drüber:	1	= -2⋅52 +15⋅(59 -1⋅ 52) = -2⋅52 +15⋅59 -15⋅ 52) = 15⋅59 -17⋅ 52 (=1)

Es gilt also: ggt(59,52)=1 = 15⋅59 -17⋅52

oder wenn man 15⋅59 auf die linke Seite bringt:

1 -15⋅59 = -17⋅52

-17⋅52 = -15⋅59 + 1 |+59⋅52

-17⋅52 + 59⋅52 = -15⋅59 + 59⋅52 + 1

(-17 + 59) ⋅ 52 = (-15 + 52) ⋅ 59 + 1

42⋅52 = 37⋅59 + 1

Es gilt also: 42⋅52 = 37⋅59 +1

Somit 42⋅52 = 1 mod 59

42 ist also das Inverse von 52 mod 59