Um längere Rechnungen zu vermeiden, rechnen wir:

(502 - 2498) mod 5 ≡ (502 mod 5 - 2498 mod 5) mod 5.

502 mod 5 ≡ 2 mod 5 kann man relativ leicht bestimmen, weil ja 502 = 500+2 = 5 ⋅ 100 +2.

2498 mod 5 ≡ 3 mod 5 kann man relativ leicht bestimmen, weil ja 2498 = 2400+98 = 5 ⋅ 480 +98.

Somit gilt:

(502 - 2498) mod 5 ≡ (2 - 3) mod 5 ≡ -1 mod 5 ≡ 4 mod 5.

Um längere Rechnungen zu vermeiden, rechnen wir:

(90 ⋅ 22) mod 8 ≡ (90 mod 8 ⋅ 22 mod 8) mod 8.

90 mod 8 ≡ 2 mod 8 kann man relativ leicht bestimmen, weil ja 90 = 88 + 2 = 11 ⋅ 8 + 2 ist.

22 mod 8 ≡ 6 mod 8 kann man relativ leicht bestimmen, weil ja 22 = 16 + 6 = 2 ⋅ 8 + 6 ist.

Somit gilt:

(90 ⋅ 22) mod 8 ≡ (2 ⋅ 6) mod 8 ≡ 12 mod 8 ≡ 4 mod 8.

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

2: 622²=622¹⁺¹=622¹⋅622¹ ≡ 622⋅622=386884 ≡ 317 mod 677

4: 622⁴=622²⁺²=622²⋅622² ≡ 317⋅317=100489 ≡ 293 mod 677

8: 622⁸=622⁴⁺⁴=622⁴⋅622⁴ ≡ 293⋅293=85849 ≡ 547 mod 677

16: 622¹⁶=622⁸⁺⁸=622⁸⋅622⁸ ≡ 547⋅547=299209 ≡ 652 mod 677

32: 622³²=622¹⁶⁺¹⁶=622¹⁶⋅622¹⁶ ≡ 652⋅652=425104 ≡ 625 mod 677

64: 622⁶⁴=622³²⁺³²=622³²⋅622³² ≡ 625⋅625=390625 ≡ 673 mod 677

128: 622¹²⁸=622⁶⁴⁺⁶⁴=622⁶⁴⋅622⁶⁴ ≡ 673⋅673=452929 ≡ 16 mod 677

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

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

167 = 128+32+4+2+1

314¹⁶⁷

= 314^128+32+4+2+1

= 314¹²⁸⋅314³²⋅314⁴⋅314²⋅314¹

≡ 264 ⋅ 195 ⋅ 348 ⋅ 240 ⋅ 314 mod 367
≡ 51480 ⋅ 348 ⋅ 240 ⋅ 314 mod 367 ≡ 100 ⋅ 348 ⋅ 240 ⋅ 314 mod 367
≡ 34800 ⋅ 240 ⋅ 314 mod 367 ≡ 302 ⋅ 240 ⋅ 314 mod 367
≡ 72480 ⋅ 314 mod 367 ≡ 181 ⋅ 314 mod 367
≡ 56834 mod 367 ≡ 316 mod 367

Es gilt also: 314¹⁶⁷ ≡ 316 mod 367

Berechnung des größten gemeinsamen Teilers von 71 und 63

=>71	= 1⋅63 + 8
=>63	= 7⋅8 + 7
=>8	= 1⋅7 + 1
=>7	= 7⋅1 + 0

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

Es gilt also: ggt(71,63)=1 = 8⋅71 -9⋅63

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

1 -8⋅71 = -9⋅63

-9⋅63 = -8⋅71 + 1 |+71⋅63

-9⋅63 + 71⋅63 = -8⋅71 + 71⋅63 + 1

(-9 + 71) ⋅ 63 = (-8 + 63) ⋅ 71 + 1

62⋅63 = 55⋅71 + 1

Es gilt also: 62⋅63 = 55⋅71 +1

Somit 62⋅63 = 1 mod 71

62 ist also das Inverse von 63 mod 71