Um längere Rechnungen zu vermeiden, rechnen wir:

(299 - 6001) mod 3 ≡ (299 mod 3 - 6001 mod 3) mod 3.

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

6001 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 6001 = 6000+1 = 3 ⋅ 2000 +1.

Somit gilt:

(299 - 6001) mod 3 ≡ (2 - 1) mod 3 ≡ 1 mod 3.

Um längere Rechnungen zu vermeiden, rechnen wir:

(52 ⋅ 15) mod 7 ≡ (52 mod 7 ⋅ 15 mod 7) mod 7.

52 mod 7 ≡ 3 mod 7 kann man relativ leicht bestimmen, weil ja 52 = 49 + 3 = 7 ⋅ 7 + 3 ist.

15 mod 7 ≡ 1 mod 7 kann man relativ leicht bestimmen, weil ja 15 = 14 + 1 = 2 ⋅ 7 + 1 ist.

Somit gilt:

(52 ⋅ 15) mod 7 ≡ (3 ⋅ 1) mod 7 ≡ 3 mod 7.

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

2: 217²=217¹⁺¹=217¹⋅217¹ ≡ 217⋅217=47089 ≡ 261 mod 509

4: 217⁴=217²⁺²=217²⋅217² ≡ 261⋅261=68121 ≡ 424 mod 509

8: 217⁸=217⁴⁺⁴=217⁴⋅217⁴ ≡ 424⋅424=179776 ≡ 99 mod 509

16: 217¹⁶=217⁸⁺⁸=217⁸⋅217⁸ ≡ 99⋅99=9801 ≡ 130 mod 509

32: 217³²=217¹⁶⁺¹⁶=217¹⁶⋅217¹⁶ ≡ 130⋅130=16900 ≡ 103 mod 509

64: 217⁶⁴=217³²⁺³²=217³²⋅217³² ≡ 103⋅103=10609 ≡ 429 mod 509

128: 217¹²⁸=217⁶⁴⁺⁶⁴=217⁶⁴⋅217⁶⁴ ≡ 429⋅429=184041 ≡ 292 mod 509

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

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

103 = 64+32+4+2+1

442¹⁰³

= 442^64+32+4+2+1

= 442⁶⁴⋅442³²⋅442⁴⋅442²⋅442¹

≡ 24 ⋅ 445 ⋅ 320 ⋅ 417 ⋅ 442 mod 509
≡ 10680 ⋅ 320 ⋅ 417 ⋅ 442 mod 509 ≡ 500 ⋅ 320 ⋅ 417 ⋅ 442 mod 509
≡ 160000 ⋅ 417 ⋅ 442 mod 509 ≡ 174 ⋅ 417 ⋅ 442 mod 509
≡ 72558 ⋅ 442 mod 509 ≡ 280 ⋅ 442 mod 509
≡ 123760 mod 509 ≡ 73 mod 509

Es gilt also: 442¹⁰³ ≡ 73 mod 509

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

=>59	= 1⋅39 + 20
=>39	= 1⋅20 + 19
=>20	= 1⋅19 + 1
=>19	= 19⋅1 + 0

also gilt: ggt(59,39)=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= 20-1⋅19
19= 39-1⋅20	eingesetzt in die Zeile drüber:	1	= 1⋅20 -1⋅(39 -1⋅ 20) = 1⋅20 -1⋅39 +1⋅ 20) = -1⋅39 +2⋅ 20 (=1)
20= 59-1⋅39	eingesetzt in die Zeile drüber:	1	= -1⋅39 +2⋅(59 -1⋅ 39) = -1⋅39 +2⋅59 -2⋅ 39) = 2⋅59 -3⋅ 39 (=1)

Es gilt also: ggt(59,39)=1 = 2⋅59 -3⋅39

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

1 -2⋅59 = -3⋅39

-3⋅39 = -2⋅59 + 1 |+59⋅39

-3⋅39 + 59⋅39 = -2⋅59 + 59⋅39 + 1

(-3 + 59) ⋅ 39 = (-2 + 39) ⋅ 59 + 1

56⋅39 = 37⋅59 + 1

Es gilt also: 56⋅39 = 37⋅59 +1

Somit 56⋅39 = 1 mod 59

56 ist also das Inverse von 39 mod 59