Um längere Rechnungen zu vermeiden, rechnen wir:

(1801 - 3000) mod 6 ≡ (1801 mod 6 - 3000 mod 6) mod 6.

1801 mod 6 ≡ 1 mod 6 kann man relativ leicht bestimmen, weil ja 1801 = 1800+1 = 6 ⋅ 300 +1.

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

Somit gilt:

(1801 - 3000) mod 6 ≡ (1 - 0) mod 6 ≡ 1 mod 6.

Um längere Rechnungen zu vermeiden, rechnen wir:

(51 ⋅ 88) mod 6 ≡ (51 mod 6 ⋅ 88 mod 6) mod 6.

51 mod 6 ≡ 3 mod 6 kann man relativ leicht bestimmen, weil ja 51 = 48 + 3 = 8 ⋅ 6 + 3 ist.

88 mod 6 ≡ 4 mod 6 kann man relativ leicht bestimmen, weil ja 88 = 84 + 4 = 14 ⋅ 6 + 4 ist.

Somit gilt:

(51 ⋅ 88) mod 6 ≡ (3 ⋅ 4) mod 6 ≡ 12 mod 6 ≡ 0 mod 6.

Die 32 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: 257¹=257

2: 257²=257¹⁺¹=257¹⋅257¹ ≡ 257⋅257=66049 ≡ 196 mod 271

4: 257⁴=257²⁺²=257²⋅257² ≡ 196⋅196=38416 ≡ 205 mod 271

8: 257⁸=257⁴⁺⁴=257⁴⋅257⁴ ≡ 205⋅205=42025 ≡ 20 mod 271

16: 257¹⁶=257⁸⁺⁸=257⁸⋅257⁸ ≡ 20⋅20=400 ≡ 129 mod 271

32: 257³²=257¹⁶⁺¹⁶=257¹⁶⋅257¹⁶ ≡ 129⋅129=16641 ≡ 110 mod 271

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

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

248 = 128+64+32+16+8

365²⁴⁸

= 365^{128+64+32+16+8}

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

≡ 210 ⋅ 364 ⋅ 508 ⋅ 755 ⋅ 303 mod 859
≡ 76440 ⋅ 508 ⋅ 755 ⋅ 303 mod 859 ≡ 848 ⋅ 508 ⋅ 755 ⋅ 303 mod 859
≡ 430784 ⋅ 755 ⋅ 303 mod 859 ≡ 425 ⋅ 755 ⋅ 303 mod 859
≡ 320875 ⋅ 303 mod 859 ≡ 468 ⋅ 303 mod 859
≡ 141804 mod 859 ≡ 69 mod 859

Es gilt also: 365²⁴⁸ ≡ 69 mod 859

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

=>83	= 1⋅74 + 9
=>74	= 8⋅9 + 2
=>9	= 4⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(83,74)=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-4⋅2
2= 74-8⋅9	eingesetzt in die Zeile drüber:	1	= 1⋅9 -4⋅(74 -8⋅ 9) = 1⋅9 -4⋅74 +32⋅ 9) = -4⋅74 +33⋅ 9 (=1)
9= 83-1⋅74	eingesetzt in die Zeile drüber:	1	= -4⋅74 +33⋅(83 -1⋅ 74) = -4⋅74 +33⋅83 -33⋅ 74) = 33⋅83 -37⋅ 74 (=1)

Es gilt also: ggt(83,74)=1 = 33⋅83 -37⋅74

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

1 -33⋅83 = -37⋅74

-37⋅74 = -33⋅83 + 1 |+83⋅74

-37⋅74 + 83⋅74 = -33⋅83 + 83⋅74 + 1

(-37 + 83) ⋅ 74 = (-33 + 74) ⋅ 83 + 1

46⋅74 = 41⋅83 + 1

Es gilt also: 46⋅74 = 41⋅83 +1

Somit 46⋅74 = 1 mod 83

46 ist also das Inverse von 74 mod 83