Um längere Rechnungen zu vermeiden, rechnen wir:

(149 - 1501) mod 3 ≡ (149 mod 3 - 1501 mod 3) mod 3.

149 mod 3 ≡ 2 mod 3 kann man relativ leicht bestimmen, weil ja 149 = 150-1 = 3 ⋅ 50 -1 = 3 ⋅ 50 - 3 + 2.

1501 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 1501 = 1500+1 = 3 ⋅ 500 +1.

Somit gilt:

(149 - 1501) mod 3 ≡ (2 - 1) mod 3 ≡ 1 mod 3.

Um längere Rechnungen zu vermeiden, rechnen wir:

(19 ⋅ 59) mod 7 ≡ (19 mod 7 ⋅ 59 mod 7) mod 7.

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

59 mod 7 ≡ 3 mod 7 kann man relativ leicht bestimmen, weil ja 59 = 56 + 3 = 8 ⋅ 7 + 3 ist.

Somit gilt:

(19 ⋅ 59) mod 7 ≡ (5 ⋅ 3) mod 7 ≡ 15 mod 7 ≡ 1 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: 346¹=346

2: 346²=346¹⁺¹=346¹⋅346¹ ≡ 346⋅346=119716 ≡ 308 mod 439

4: 346⁴=346²⁺²=346²⋅346² ≡ 308⋅308=94864 ≡ 40 mod 439

8: 346⁸=346⁴⁺⁴=346⁴⋅346⁴ ≡ 40⋅40=1600 ≡ 283 mod 439

16: 346¹⁶=346⁸⁺⁸=346⁸⋅346⁸ ≡ 283⋅283=80089 ≡ 191 mod 439

32: 346³²=346¹⁶⁺¹⁶=346¹⁶⋅346¹⁶ ≡ 191⋅191=36481 ≡ 44 mod 439

64: 346⁶⁴=346³²⁺³²=346³²⋅346³² ≡ 44⋅44=1936 ≡ 180 mod 439

128: 346¹²⁸=346⁶⁴⁺⁶⁴=346⁶⁴⋅346⁶⁴ ≡ 180⋅180=32400 ≡ 353 mod 439

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

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

207 = 128+64+8+4+2+1

343²⁰⁷

= 343^{128+64+8+4+2+1}

= 343¹²⁸⋅343⁶⁴⋅343⁸⋅343⁴⋅343²⋅343¹

≡ 490 ⋅ 64 ⋅ 128 ⋅ 574 ⋅ 454 ⋅ 343 mod 601
≡ 31360 ⋅ 128 ⋅ 574 ⋅ 454 ⋅ 343 mod 601 ≡ 108 ⋅ 128 ⋅ 574 ⋅ 454 ⋅ 343 mod 601
≡ 13824 ⋅ 574 ⋅ 454 ⋅ 343 mod 601 ≡ 1 ⋅ 574 ⋅ 454 ⋅ 343 mod 601
≡ 574 ⋅ 454 ⋅ 343 mod 601
≡ 260596 ⋅ 343 mod 601 ≡ 363 ⋅ 343 mod 601
≡ 124509 mod 601 ≡ 102 mod 601

Es gilt also: 343²⁰⁷ ≡ 102 mod 601

Berechnung des größten gemeinsamen Teilers von 73 und 48

=>73	= 1⋅48 + 25
=>48	= 1⋅25 + 23
=>25	= 1⋅23 + 2
=>23	= 11⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(73,48)=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= 23-11⋅2
2= 25-1⋅23	eingesetzt in die Zeile drüber:	1	= 1⋅23 -11⋅(25 -1⋅ 23) = 1⋅23 -11⋅25 +11⋅ 23) = -11⋅25 +12⋅ 23 (=1)
23= 48-1⋅25	eingesetzt in die Zeile drüber:	1	= -11⋅25 +12⋅(48 -1⋅ 25) = -11⋅25 +12⋅48 -12⋅ 25) = 12⋅48 -23⋅ 25 (=1)
25= 73-1⋅48	eingesetzt in die Zeile drüber:	1	= 12⋅48 -23⋅(73 -1⋅ 48) = 12⋅48 -23⋅73 +23⋅ 48) = -23⋅73 +35⋅ 48 (=1)

Es gilt also: ggt(73,48)=1 = -23⋅73 +35⋅48

oder wenn man -23⋅73 auf die linke Seite bringt:

1 +23⋅73 = +35⋅48

Es gilt also: 35⋅48 = 23⋅73 +1

Somit 35⋅48 = 1 mod 73

35 ist also das Inverse von 48 mod 73