Um längere Rechnungen zu vermeiden, rechnen wir:

(2501 - 2001) mod 5 ≡ (2501 mod 5 - 2001 mod 5) mod 5.

2501 mod 5 ≡ 1 mod 5 kann man relativ leicht bestimmen, weil ja 2501 = 2500+1 = 5 ⋅ 500 +1.

2001 mod 5 ≡ 1 mod 5 kann man relativ leicht bestimmen, weil ja 2001 = 2000+1 = 5 ⋅ 400 +1.

Somit gilt:

(2501 - 2001) mod 5 ≡ (1 - 1) mod 5 ≡ 0 mod 5.

Um längere Rechnungen zu vermeiden, rechnen wir:

(55 ⋅ 76) mod 9 ≡ (55 mod 9 ⋅ 76 mod 9) mod 9.

55 mod 9 ≡ 1 mod 9 kann man relativ leicht bestimmen, weil ja 55 = 54 + 1 = 6 ⋅ 9 + 1 ist.

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

Somit gilt:

(55 ⋅ 76) mod 9 ≡ (1 ⋅ 4) mod 9 ≡ 4 mod 9.

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

2: 853²=853¹⁺¹=853¹⋅853¹ ≡ 853⋅853=727609 ≡ 100 mod 863

4: 853⁴=853²⁺²=853²⋅853² ≡ 100⋅100=10000 ≡ 507 mod 863

8: 853⁸=853⁴⁺⁴=853⁴⋅853⁴ ≡ 507⋅507=257049 ≡ 738 mod 863

16: 853¹⁶=853⁸⁺⁸=853⁸⋅853⁸ ≡ 738⋅738=544644 ≡ 91 mod 863

32: 853³²=853¹⁶⁺¹⁶=853¹⁶⋅853¹⁶ ≡ 91⋅91=8281 ≡ 514 mod 863

64: 853⁶⁴=853³²⁺³²=853³²⋅853³² ≡ 514⋅514=264196 ≡ 118 mod 863

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

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

239 = 128+64+32+8+4+2+1

158²³⁹

= 158^{128+64+32+8+4+2+1}

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

≡ 138 ⋅ 140 ⋅ 156 ⋅ 124 ⋅ 178 ⋅ 242 ⋅ 158 mod 263
≡ 19320 ⋅ 156 ⋅ 124 ⋅ 178 ⋅ 242 ⋅ 158 mod 263 ≡ 121 ⋅ 156 ⋅ 124 ⋅ 178 ⋅ 242 ⋅ 158 mod 263
≡ 18876 ⋅ 124 ⋅ 178 ⋅ 242 ⋅ 158 mod 263 ≡ 203 ⋅ 124 ⋅ 178 ⋅ 242 ⋅ 158 mod 263
≡ 25172 ⋅ 178 ⋅ 242 ⋅ 158 mod 263 ≡ 187 ⋅ 178 ⋅ 242 ⋅ 158 mod 263
≡ 33286 ⋅ 242 ⋅ 158 mod 263 ≡ 148 ⋅ 242 ⋅ 158 mod 263
≡ 35816 ⋅ 158 mod 263 ≡ 48 ⋅ 158 mod 263
≡ 7584 mod 263 ≡ 220 mod 263

Es gilt also: 158²³⁹ ≡ 220 mod 263

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

=>59	= 1⋅53 + 6
=>53	= 8⋅6 + 5
=>6	= 1⋅5 + 1
=>5	= 5⋅1 + 0

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

Es gilt also: ggt(59,53)=1 = 9⋅59 -10⋅53

oder wenn man 9⋅59 auf die linke Seite bringt:

1 -9⋅59 = -10⋅53

-10⋅53 = -9⋅59 + 1 |+59⋅53

-10⋅53 + 59⋅53 = -9⋅59 + 59⋅53 + 1

(-10 + 59) ⋅ 53 = (-9 + 53) ⋅ 59 + 1

49⋅53 = 44⋅59 + 1

Es gilt also: 49⋅53 = 44⋅59 +1

Somit 49⋅53 = 1 mod 59

49 ist also das Inverse von 53 mod 59