Um längere Rechnungen zu vermeiden, rechnen wir:

(498 - 1996) mod 5 ≡ (498 mod 5 - 1996 mod 5) mod 5.

498 mod 5 ≡ 3 mod 5 kann man relativ leicht bestimmen, weil ja 498 = 400+98 = 5 ⋅ 80 +98.

1996 mod 5 ≡ 1 mod 5 kann man relativ leicht bestimmen, weil ja 1996 = 1900+96 = 5 ⋅ 380 +96.

Somit gilt:

(498 - 1996) mod 5 ≡ (3 - 1) mod 5 ≡ 2 mod 5.

Um längere Rechnungen zu vermeiden, rechnen wir:

(61 ⋅ 75) mod 8 ≡ (61 mod 8 ⋅ 75 mod 8) mod 8.

61 mod 8 ≡ 5 mod 8 kann man relativ leicht bestimmen, weil ja 61 = 56 + 5 = 7 ⋅ 8 + 5 ist.

75 mod 8 ≡ 3 mod 8 kann man relativ leicht bestimmen, weil ja 75 = 72 + 3 = 9 ⋅ 8 + 3 ist.

Somit gilt:

(61 ⋅ 75) mod 8 ≡ (5 ⋅ 3) mod 8 ≡ 15 mod 8 ≡ 7 mod 8.

Die 8 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: 159¹=159

2: 159²=159¹⁺¹=159¹⋅159¹ ≡ 159⋅159=25281 ≡ 264 mod 269

4: 159⁴=159²⁺²=159²⋅159² ≡ 264⋅264=69696 ≡ 25 mod 269

8: 159⁸=159⁴⁺⁴=159⁴⋅159⁴ ≡ 25⋅25=625 ≡ 87 mod 269

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

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

245 = 128+64+32+16+4+1

146²⁴⁵

= 146^{128+64+32+16+4+1}

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

≡ 213 ⋅ 80 ⋅ 235 ⋅ 226 ⋅ 190 ⋅ 146 mod 269
≡ 17040 ⋅ 235 ⋅ 226 ⋅ 190 ⋅ 146 mod 269 ≡ 93 ⋅ 235 ⋅ 226 ⋅ 190 ⋅ 146 mod 269
≡ 21855 ⋅ 226 ⋅ 190 ⋅ 146 mod 269 ≡ 66 ⋅ 226 ⋅ 190 ⋅ 146 mod 269
≡ 14916 ⋅ 190 ⋅ 146 mod 269 ≡ 121 ⋅ 190 ⋅ 146 mod 269
≡ 22990 ⋅ 146 mod 269 ≡ 125 ⋅ 146 mod 269
≡ 18250 mod 269 ≡ 227 mod 269

Es gilt also: 146²⁴⁵ ≡ 227 mod 269

Berechnung des größten gemeinsamen Teilers von 89 und 36

=>89	= 2⋅36 + 17
=>36	= 2⋅17 + 2
=>17	= 8⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(89,36)=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= 17-8⋅2
2= 36-2⋅17	eingesetzt in die Zeile drüber:	1	= 1⋅17 -8⋅(36 -2⋅ 17) = 1⋅17 -8⋅36 +16⋅ 17) = -8⋅36 +17⋅ 17 (=1)
17= 89-2⋅36	eingesetzt in die Zeile drüber:	1	= -8⋅36 +17⋅(89 -2⋅ 36) = -8⋅36 +17⋅89 -34⋅ 36) = 17⋅89 -42⋅ 36 (=1)

Es gilt also: ggt(89,36)=1 = 17⋅89 -42⋅36

oder wenn man 17⋅89 auf die linke Seite bringt:

1 -17⋅89 = -42⋅36

-42⋅36 = -17⋅89 + 1 |+89⋅36

-42⋅36 + 89⋅36 = -17⋅89 + 89⋅36 + 1

(-42 + 89) ⋅ 36 = (-17 + 36) ⋅ 89 + 1

47⋅36 = 19⋅89 + 1

Es gilt also: 47⋅36 = 19⋅89 +1

Somit 47⋅36 = 1 mod 89

47 ist also das Inverse von 36 mod 89