Um längere Rechnungen zu vermeiden, rechnen wir:

(12002 - 24003) mod 6 ≡ (12002 mod 6 - 24003 mod 6) mod 6.

12002 mod 6 ≡ 2 mod 6 kann man relativ leicht bestimmen, weil ja 12002 = 12000+2 = 6 ⋅ 2000 +2.

24003 mod 6 ≡ 3 mod 6 kann man relativ leicht bestimmen, weil ja 24003 = 24000+3 = 6 ⋅ 4000 +3.

Somit gilt:

(12002 - 24003) mod 6 ≡ (2 - 3) mod 6 ≡ -1 mod 6 ≡ 5 mod 6.

Um längere Rechnungen zu vermeiden, rechnen wir:

(31 ⋅ 19) mod 10 ≡ (31 mod 10 ⋅ 19 mod 10) mod 10.

31 mod 10 ≡ 1 mod 10 kann man relativ leicht bestimmen, weil ja 31 = 30 + 1 = 3 ⋅ 10 + 1 ist.

19 mod 10 ≡ 9 mod 10 kann man relativ leicht bestimmen, weil ja 19 = 10 + 9 = 1 ⋅ 10 + 9 ist.

Somit gilt:

(31 ⋅ 19) mod 10 ≡ (1 ⋅ 9) mod 10 ≡ 9 mod 10.

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

2: 286²=286¹⁺¹=286¹⋅286¹ ≡ 286⋅286=81796 ≡ 258 mod 691

4: 286⁴=286²⁺²=286²⋅286² ≡ 258⋅258=66564 ≡ 228 mod 691

8: 286⁸=286⁴⁺⁴=286⁴⋅286⁴ ≡ 228⋅228=51984 ≡ 159 mod 691

16: 286¹⁶=286⁸⁺⁸=286⁸⋅286⁸ ≡ 159⋅159=25281 ≡ 405 mod 691

32: 286³²=286¹⁶⁺¹⁶=286¹⁶⋅286¹⁶ ≡ 405⋅405=164025 ≡ 258 mod 691

64: 286⁶⁴=286³²⁺³²=286³²⋅286³² ≡ 258⋅258=66564 ≡ 228 mod 691

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

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

211 = 128+64+16+2+1

284²¹¹

= 284^{128+64+16+2+1}

= 284¹²⁸⋅284⁶⁴⋅284¹⁶⋅284²⋅284¹

≡ 421 ⋅ 255 ⋅ 18 ⋅ 422 ⋅ 284 mod 521
≡ 107355 ⋅ 18 ⋅ 422 ⋅ 284 mod 521 ≡ 29 ⋅ 18 ⋅ 422 ⋅ 284 mod 521
≡ 522 ⋅ 422 ⋅ 284 mod 521 ≡ 1 ⋅ 422 ⋅ 284 mod 521
≡ 422 ⋅ 284 mod 521
≡ 119848 mod 521 ≡ 18 mod 521

Es gilt also: 284²¹¹ ≡ 18 mod 521

Berechnung des größten gemeinsamen Teilers von 101 und 48

=>101	= 2⋅48 + 5
=>48	= 9⋅5 + 3
=>5	= 1⋅3 + 2
=>3	= 1⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(101,48)=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= 3-1⋅2
2= 5-1⋅3	eingesetzt in die Zeile drüber:	1	= 1⋅3 -1⋅(5 -1⋅ 3) = 1⋅3 -1⋅5 +1⋅ 3) = -1⋅5 +2⋅ 3 (=1)
3= 48-9⋅5	eingesetzt in die Zeile drüber:	1	= -1⋅5 +2⋅(48 -9⋅ 5) = -1⋅5 +2⋅48 -18⋅ 5) = 2⋅48 -19⋅ 5 (=1)
5= 101-2⋅48	eingesetzt in die Zeile drüber:	1	= 2⋅48 -19⋅(101 -2⋅ 48) = 2⋅48 -19⋅101 +38⋅ 48) = -19⋅101 +40⋅ 48 (=1)

Es gilt also: ggt(101,48)=1 = -19⋅101 +40⋅48

oder wenn man -19⋅101 auf die linke Seite bringt:

1 +19⋅101 = +40⋅48

Es gilt also: 40⋅48 = 19⋅101 +1

Somit 40⋅48 = 1 mod 101

40 ist also das Inverse von 48 mod 101