Um längere Rechnungen zu vermeiden, rechnen wir:

(8002 + 2002) mod 4 ≡ (8002 mod 4 + 2002 mod 4) mod 4.

8002 mod 4 ≡ 2 mod 4 kann man relativ leicht bestimmen, weil ja 8002 = 8000+2 = 4 ⋅ 2000 +2.

2002 mod 4 ≡ 2 mod 4 kann man relativ leicht bestimmen, weil ja 2002 = 2000+2 = 4 ⋅ 500 +2.

Somit gilt:

(8002 + 2002) mod 4 ≡ (2 + 2) mod 4 ≡ 4 mod 4 ≡ 0 mod 4.

Um längere Rechnungen zu vermeiden, rechnen wir:

(49 ⋅ 18) mod 4 ≡ (49 mod 4 ⋅ 18 mod 4) mod 4.

49 mod 4 ≡ 1 mod 4 kann man relativ leicht bestimmen, weil ja 49 = 48 + 1 = 12 ⋅ 4 + 1 ist.

18 mod 4 ≡ 2 mod 4 kann man relativ leicht bestimmen, weil ja 18 = 16 + 2 = 4 ⋅ 4 + 2 ist.

Somit gilt:

(49 ⋅ 18) mod 4 ≡ (1 ⋅ 2) mod 4 ≡ 2 mod 4.

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

2: 481²=481¹⁺¹=481¹⋅481¹ ≡ 481⋅481=231361 ≡ 275 mod 509

4: 481⁴=481²⁺²=481²⋅481² ≡ 275⋅275=75625 ≡ 293 mod 509

8: 481⁸=481⁴⁺⁴=481⁴⋅481⁴ ≡ 293⋅293=85849 ≡ 337 mod 509

16: 481¹⁶=481⁸⁺⁸=481⁸⋅481⁸ ≡ 337⋅337=113569 ≡ 62 mod 509

32: 481³²=481¹⁶⁺¹⁶=481¹⁶⋅481¹⁶ ≡ 62⋅62=3844 ≡ 281 mod 509

64: 481⁶⁴=481³²⁺³²=481³²⋅481³² ≡ 281⋅281=78961 ≡ 66 mod 509

128: 481¹²⁸=481⁶⁴⁺⁶⁴=481⁶⁴⋅481⁶⁴ ≡ 66⋅66=4356 ≡ 284 mod 509

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

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

87 = 64+16+4+2+1

852⁸⁷

= 852^64+16+4+2+1

= 852⁶⁴⋅852¹⁶⋅852⁴⋅852²⋅852¹

≡ 905 ⋅ 501 ⋅ 49 ⋅ 970 ⋅ 852 mod 977
≡ 453405 ⋅ 49 ⋅ 970 ⋅ 852 mod 977 ≡ 77 ⋅ 49 ⋅ 970 ⋅ 852 mod 977
≡ 3773 ⋅ 970 ⋅ 852 mod 977 ≡ 842 ⋅ 970 ⋅ 852 mod 977
≡ 816740 ⋅ 852 mod 977 ≡ 945 ⋅ 852 mod 977
≡ 805140 mod 977 ≡ 92 mod 977

Es gilt also: 852⁸⁷ ≡ 92 mod 977

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

=>89	= 1⋅52 + 37
=>52	= 1⋅37 + 15
=>37	= 2⋅15 + 7
=>15	= 2⋅7 + 1
=>7	= 7⋅1 + 0

also gilt: ggt(89,52)=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= 15-2⋅7
7= 37-2⋅15	eingesetzt in die Zeile drüber:	1	= 1⋅15 -2⋅(37 -2⋅ 15) = 1⋅15 -2⋅37 +4⋅ 15) = -2⋅37 +5⋅ 15 (=1)
15= 52-1⋅37	eingesetzt in die Zeile drüber:	1	= -2⋅37 +5⋅(52 -1⋅ 37) = -2⋅37 +5⋅52 -5⋅ 37) = 5⋅52 -7⋅ 37 (=1)
37= 89-1⋅52	eingesetzt in die Zeile drüber:	1	= 5⋅52 -7⋅(89 -1⋅ 52) = 5⋅52 -7⋅89 +7⋅ 52) = -7⋅89 +12⋅ 52 (=1)

Es gilt also: ggt(89,52)=1 = -7⋅89 +12⋅52

oder wenn man -7⋅89 auf die linke Seite bringt:

1 +7⋅89 = +12⋅52

Es gilt also: 12⋅52 = 7⋅89 +1

Somit 12⋅52 = 1 mod 89

12 ist also das Inverse von 52 mod 89