Um längere Rechnungen zu vermeiden, rechnen wir:

(297 + 1500) mod 3 ≡ (297 mod 3 + 1500 mod 3) mod 3.

297 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 297 = 300-3 = 3 ⋅ 100 -3 = 3 ⋅ 100 - 3 + 0.

1500 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 1500 = 1500+0 = 3 ⋅ 500 +0.

Somit gilt:

(297 + 1500) mod 3 ≡ (0 + 0) mod 3 ≡ 0 mod 3.

Um längere Rechnungen zu vermeiden, rechnen wir:

(98 ⋅ 18) mod 9 ≡ (98 mod 9 ⋅ 18 mod 9) mod 9.

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

18 mod 9 ≡ 0 mod 9 kann man relativ leicht bestimmen, weil ja 18 = 18 + 0 = 2 ⋅ 9 + 0 ist.

Somit gilt:

(98 ⋅ 18) mod 9 ≡ (8 ⋅ 0) mod 9 ≡ 0 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: 520¹=520

2: 520²=520¹⁺¹=520¹⋅520¹ ≡ 520⋅520=270400 ≡ 56 mod 719

4: 520⁴=520²⁺²=520²⋅520² ≡ 56⋅56=3136 ≡ 260 mod 719

8: 520⁸=520⁴⁺⁴=520⁴⋅520⁴ ≡ 260⋅260=67600 ≡ 14 mod 719

16: 520¹⁶=520⁸⁺⁸=520⁸⋅520⁸ ≡ 14⋅14=196 ≡ 196 mod 719

32: 520³²=520¹⁶⁺¹⁶=520¹⁶⋅520¹⁶ ≡ 196⋅196=38416 ≡ 309 mod 719

64: 520⁶⁴=520³²⁺³²=520³²⋅520³² ≡ 309⋅309=95481 ≡ 573 mod 719

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

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

213 = 128+64+16+4+1

433²¹³

= 433^{128+64+16+4+1}

= 433¹²⁸⋅433⁶⁴⋅433¹⁶⋅433⁴⋅433¹

≡ 359 ⋅ 324 ⋅ 359 ⋅ 431 ⋅ 433 mod 449
≡ 116316 ⋅ 359 ⋅ 431 ⋅ 433 mod 449 ≡ 25 ⋅ 359 ⋅ 431 ⋅ 433 mod 449
≡ 8975 ⋅ 431 ⋅ 433 mod 449 ≡ 444 ⋅ 431 ⋅ 433 mod 449
≡ 191364 ⋅ 433 mod 449 ≡ 90 ⋅ 433 mod 449
≡ 38970 mod 449 ≡ 356 mod 449

Es gilt also: 433²¹³ ≡ 356 mod 449

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

=>59	= 1⋅39 + 20
=>39	= 1⋅20 + 19
=>20	= 1⋅19 + 1
=>19	= 19⋅1 + 0

also gilt: ggt(59,39)=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= 20-1⋅19
19= 39-1⋅20	eingesetzt in die Zeile drüber:	1	= 1⋅20 -1⋅(39 -1⋅ 20) = 1⋅20 -1⋅39 +1⋅ 20) = -1⋅39 +2⋅ 20 (=1)
20= 59-1⋅39	eingesetzt in die Zeile drüber:	1	= -1⋅39 +2⋅(59 -1⋅ 39) = -1⋅39 +2⋅59 -2⋅ 39) = 2⋅59 -3⋅ 39 (=1)

Es gilt also: ggt(59,39)=1 = 2⋅59 -3⋅39

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

1 -2⋅59 = -3⋅39

-3⋅39 = -2⋅59 + 1 |+59⋅39

-3⋅39 + 59⋅39 = -2⋅59 + 59⋅39 + 1

(-3 + 59) ⋅ 39 = (-2 + 39) ⋅ 59 + 1

56⋅39 = 37⋅59 + 1

Es gilt also: 56⋅39 = 37⋅59 +1

Somit 56⋅39 = 1 mod 59

56 ist also das Inverse von 39 mod 59