Um längere Rechnungen zu vermeiden, rechnen wir:

(302 + 15002) mod 3 ≡ (302 mod 3 + 15002 mod 3) mod 3.

302 mod 3 ≡ 2 mod 3 kann man relativ leicht bestimmen, weil ja 302 = 300+2 = 3 ⋅ 100 +2.

15002 mod 3 ≡ 2 mod 3 kann man relativ leicht bestimmen, weil ja 15002 = 15000+2 = 3 ⋅ 5000 +2.

Somit gilt:

(302 + 15002) mod 3 ≡ (2 + 2) mod 3 ≡ 4 mod 3 ≡ 1 mod 3.

Um längere Rechnungen zu vermeiden, rechnen wir:

(58 ⋅ 26) mod 5 ≡ (58 mod 5 ⋅ 26 mod 5) mod 5.

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

26 mod 5 ≡ 1 mod 5 kann man relativ leicht bestimmen, weil ja 26 = 25 + 1 = 5 ⋅ 5 + 1 ist.

Somit gilt:

(58 ⋅ 26) mod 5 ≡ (3 ⋅ 1) mod 5 ≡ 3 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: 330¹=330

2: 330²=330¹⁺¹=330¹⋅330¹ ≡ 330⋅330=108900 ≡ 282 mod 421

4: 330⁴=330²⁺²=330²⋅330² ≡ 282⋅282=79524 ≡ 376 mod 421

8: 330⁸=330⁴⁺⁴=330⁴⋅330⁴ ≡ 376⋅376=141376 ≡ 341 mod 421

16: 330¹⁶=330⁸⁺⁸=330⁸⋅330⁸ ≡ 341⋅341=116281 ≡ 85 mod 421

32: 330³²=330¹⁶⁺¹⁶=330¹⁶⋅330¹⁶ ≡ 85⋅85=7225 ≡ 68 mod 421

64: 330⁶⁴=330³²⁺³²=330³²⋅330³² ≡ 68⋅68=4624 ≡ 414 mod 421

128: 330¹²⁸=330⁶⁴⁺⁶⁴=330⁶⁴⋅330⁶⁴ ≡ 414⋅414=171396 ≡ 49 mod 421

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

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

124 = 64+32+16+8+4

216¹²⁴

= 216^64+32+16+8+4

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

≡ 400 ⋅ 20 ⋅ 27 ⋅ 584 ⋅ 610 mod 709
≡ 8000 ⋅ 27 ⋅ 584 ⋅ 610 mod 709 ≡ 201 ⋅ 27 ⋅ 584 ⋅ 610 mod 709
≡ 5427 ⋅ 584 ⋅ 610 mod 709 ≡ 464 ⋅ 584 ⋅ 610 mod 709
≡ 270976 ⋅ 610 mod 709 ≡ 138 ⋅ 610 mod 709
≡ 84180 mod 709 ≡ 518 mod 709

Es gilt also: 216¹²⁴ ≡ 518 mod 709

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

=>97	= 1⋅53 + 44
=>53	= 1⋅44 + 9
=>44	= 4⋅9 + 8
=>9	= 1⋅8 + 1
=>8	= 8⋅1 + 0

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

Es gilt also: ggt(97,53)=1 = -6⋅97 +11⋅53

oder wenn man -6⋅97 auf die linke Seite bringt:

1 +6⋅97 = +11⋅53

Es gilt also: 11⋅53 = 6⋅97 +1

Somit 11⋅53 = 1 mod 97

11 ist also das Inverse von 53 mod 97