Um längere Rechnungen zu vermeiden, rechnen wir:

(15001 - 12001) mod 3 ≡ (15001 mod 3 - 12001 mod 3) mod 3.

15001 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 15001 = 15000+1 = 3 ⋅ 5000 +1.

12001 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 12001 = 12000+1 = 3 ⋅ 4000 +1.

Somit gilt:

(15001 - 12001) mod 3 ≡ (1 - 1) mod 3 ≡ 0 mod 3.

Um längere Rechnungen zu vermeiden, rechnen wir:

(67 ⋅ 34) mod 4 ≡ (67 mod 4 ⋅ 34 mod 4) mod 4.

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

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

Somit gilt:

(67 ⋅ 34) mod 4 ≡ (3 ⋅ 2) mod 4 ≡ 6 mod 4 ≡ 2 mod 4.

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

2: 163²=163¹⁺¹=163¹⋅163¹ ≡ 163⋅163=26569 ≡ 167 mod 307

4: 163⁴=163²⁺²=163²⋅163² ≡ 167⋅167=27889 ≡ 259 mod 307

8: 163⁸=163⁴⁺⁴=163⁴⋅163⁴ ≡ 259⋅259=67081 ≡ 155 mod 307

16: 163¹⁶=163⁸⁺⁸=163⁸⋅163⁸ ≡ 155⋅155=24025 ≡ 79 mod 307

32: 163³²=163¹⁶⁺¹⁶=163¹⁶⋅163¹⁶ ≡ 79⋅79=6241 ≡ 101 mod 307

64: 163⁶⁴=163³²⁺³²=163³²⋅163³² ≡ 101⋅101=10201 ≡ 70 mod 307

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

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

235 = 128+64+32+8+2+1

558²³⁵

= 558^{128+64+32+8+2+1}

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

≡ 526 ⋅ 458 ⋅ 287 ⋅ 220 ⋅ 751 ⋅ 558 mod 811
≡ 240908 ⋅ 287 ⋅ 220 ⋅ 751 ⋅ 558 mod 811 ≡ 41 ⋅ 287 ⋅ 220 ⋅ 751 ⋅ 558 mod 811
≡ 11767 ⋅ 220 ⋅ 751 ⋅ 558 mod 811 ≡ 413 ⋅ 220 ⋅ 751 ⋅ 558 mod 811
≡ 90860 ⋅ 751 ⋅ 558 mod 811 ≡ 28 ⋅ 751 ⋅ 558 mod 811
≡ 21028 ⋅ 558 mod 811 ≡ 753 ⋅ 558 mod 811
≡ 420174 mod 811 ≡ 76 mod 811

Es gilt also: 558²³⁵ ≡ 76 mod 811

Berechnung des größten gemeinsamen Teilers von 83 und 73

=>83	= 1⋅73 + 10
=>73	= 7⋅10 + 3
=>10	= 3⋅3 + 1
=>3	= 3⋅1 + 0

also gilt: ggt(83,73)=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= 10-3⋅3
3= 73-7⋅10	eingesetzt in die Zeile drüber:	1	= 1⋅10 -3⋅(73 -7⋅ 10) = 1⋅10 -3⋅73 +21⋅ 10) = -3⋅73 +22⋅ 10 (=1)
10= 83-1⋅73	eingesetzt in die Zeile drüber:	1	= -3⋅73 +22⋅(83 -1⋅ 73) = -3⋅73 +22⋅83 -22⋅ 73) = 22⋅83 -25⋅ 73 (=1)

Es gilt also: ggt(83,73)=1 = 22⋅83 -25⋅73

oder wenn man 22⋅83 auf die linke Seite bringt:

1 -22⋅83 = -25⋅73

-25⋅73 = -22⋅83 + 1 |+83⋅73

-25⋅73 + 83⋅73 = -22⋅83 + 83⋅73 + 1

(-25 + 83) ⋅ 73 = (-22 + 73) ⋅ 83 + 1

58⋅73 = 51⋅83 + 1

Es gilt also: 58⋅73 = 51⋅83 +1

Somit 58⋅73 = 1 mod 83

58 ist also das Inverse von 73 mod 83