Um längere Rechnungen zu vermeiden, rechnen wir:

(1802 + 175) mod 6 ≡ (1802 mod 6 + 175 mod 6) mod 6.

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

175 mod 6 ≡ 1 mod 6 kann man relativ leicht bestimmen, weil ja 175 = 180-5 = 6 ⋅ 30 -5 = 6 ⋅ 30 - 6 + 1.

Somit gilt:

(1802 + 175) mod 6 ≡ (2 + 1) mod 6 ≡ 3 mod 6.

Um längere Rechnungen zu vermeiden, rechnen wir:

(57 ⋅ 98) mod 5 ≡ (57 mod 5 ⋅ 98 mod 5) mod 5.

57 mod 5 ≡ 2 mod 5 kann man relativ leicht bestimmen, weil ja 57 = 55 + 2 = 11 ⋅ 5 + 2 ist.

98 mod 5 ≡ 3 mod 5 kann man relativ leicht bestimmen, weil ja 98 = 95 + 3 = 19 ⋅ 5 + 3 ist.

Somit gilt:

(57 ⋅ 98) mod 5 ≡ (2 ⋅ 3) mod 5 ≡ 6 mod 5 ≡ 1 mod 5.

Die 128 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: 458¹=458

2: 458²=458¹⁺¹=458¹⋅458¹ ≡ 458⋅458=209764 ≡ 441 mod 479

4: 458⁴=458²⁺²=458²⋅458² ≡ 441⋅441=194481 ≡ 7 mod 479

8: 458⁸=458⁴⁺⁴=458⁴⋅458⁴ ≡ 7⋅7=49 ≡ 49 mod 479

16: 458¹⁶=458⁸⁺⁸=458⁸⋅458⁸ ≡ 49⋅49=2401 ≡ 6 mod 479

32: 458³²=458¹⁶⁺¹⁶=458¹⁶⋅458¹⁶ ≡ 6⋅6=36 ≡ 36 mod 479

64: 458⁶⁴=458³²⁺³²=458³²⋅458³² ≡ 36⋅36=1296 ≡ 338 mod 479

128: 458¹²⁸=458⁶⁴⁺⁶⁴=458⁶⁴⋅458⁶⁴ ≡ 338⋅338=114244 ≡ 242 mod 479

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

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

143 = 128+8+4+2+1

333¹⁴³

= 333^128+8+4+2+1

= 333¹²⁸⋅333⁸⋅333⁴⋅333²⋅333¹

≡ 19 ⋅ 208 ⋅ 356 ⋅ 177 ⋅ 333 mod 659
≡ 3952 ⋅ 356 ⋅ 177 ⋅ 333 mod 659 ≡ 657 ⋅ 356 ⋅ 177 ⋅ 333 mod 659
≡ 233892 ⋅ 177 ⋅ 333 mod 659 ≡ 606 ⋅ 177 ⋅ 333 mod 659
≡ 107262 ⋅ 333 mod 659 ≡ 504 ⋅ 333 mod 659
≡ 167832 mod 659 ≡ 446 mod 659

Es gilt also: 333¹⁴³ ≡ 446 mod 659

Berechnung des größten gemeinsamen Teilers von 53 und 47

=>53	= 1⋅47 + 6
=>47	= 7⋅6 + 5
=>6	= 1⋅5 + 1
=>5	= 5⋅1 + 0

also gilt: ggt(53,47)=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= 6-1⋅5
5= 47-7⋅6	eingesetzt in die Zeile drüber:	1	= 1⋅6 -1⋅(47 -7⋅ 6) = 1⋅6 -1⋅47 +7⋅ 6) = -1⋅47 +8⋅ 6 (=1)
6= 53-1⋅47	eingesetzt in die Zeile drüber:	1	= -1⋅47 +8⋅(53 -1⋅ 47) = -1⋅47 +8⋅53 -8⋅ 47) = 8⋅53 -9⋅ 47 (=1)

Es gilt also: ggt(53,47)=1 = 8⋅53 -9⋅47

oder wenn man 8⋅53 auf die linke Seite bringt:

1 -8⋅53 = -9⋅47

-9⋅47 = -8⋅53 + 1 |+53⋅47

-9⋅47 + 53⋅47 = -8⋅53 + 53⋅47 + 1

(-9 + 53) ⋅ 47 = (-8 + 47) ⋅ 53 + 1

44⋅47 = 39⋅53 + 1

Es gilt also: 44⋅47 = 39⋅53 +1

Somit 44⋅47 = 1 mod 53

44 ist also das Inverse von 47 mod 53