Um längere Rechnungen zu vermeiden, rechnen wir:

(34993 + 345) mod 7 ≡ (34993 mod 7 + 345 mod 7) mod 7.

34993 mod 7 ≡ 0 mod 7 kann man relativ leicht bestimmen, weil ja 34993 = 35000-7 = 7 ⋅ 5000 -7 = 7 ⋅ 5000 - 7 + 0.

345 mod 7 ≡ 2 mod 7 kann man relativ leicht bestimmen, weil ja 345 = 350-5 = 7 ⋅ 50 -5 = 7 ⋅ 50 - 7 + 2.

Somit gilt:

(34993 + 345) mod 7 ≡ (0 + 2) mod 7 ≡ 2 mod 7.

Um längere Rechnungen zu vermeiden, rechnen wir:

(93 ⋅ 85) mod 9 ≡ (93 mod 9 ⋅ 85 mod 9) mod 9.

93 mod 9 ≡ 3 mod 9 kann man relativ leicht bestimmen, weil ja 93 = 90 + 3 = 10 ⋅ 9 + 3 ist.

85 mod 9 ≡ 4 mod 9 kann man relativ leicht bestimmen, weil ja 85 = 81 + 4 = 9 ⋅ 9 + 4 ist.

Somit gilt:

(93 ⋅ 85) mod 9 ≡ (3 ⋅ 4) mod 9 ≡ 12 mod 9 ≡ 3 mod 9.

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

2: 375²=375¹⁺¹=375¹⋅375¹ ≡ 375⋅375=140625 ≡ 275 mod 401

4: 375⁴=375²⁺²=375²⋅375² ≡ 275⋅275=75625 ≡ 237 mod 401

8: 375⁸=375⁴⁺⁴=375⁴⋅375⁴ ≡ 237⋅237=56169 ≡ 29 mod 401

16: 375¹⁶=375⁸⁺⁸=375⁸⋅375⁸ ≡ 29⋅29=841 ≡ 39 mod 401

32: 375³²=375¹⁶⁺¹⁶=375¹⁶⋅375¹⁶ ≡ 39⋅39=1521 ≡ 318 mod 401

64: 375⁶⁴=375³²⁺³²=375³²⋅375³² ≡ 318⋅318=101124 ≡ 72 mod 401

128: 375¹²⁸=375⁶⁴⁺⁶⁴=375⁶⁴⋅375⁶⁴ ≡ 72⋅72=5184 ≡ 372 mod 401

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

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

118 = 64+32+16+4+2

244¹¹⁸

= 244^64+32+16+4+2

= 244⁶⁴⋅244³²⋅244¹⁶⋅244⁴⋅244²

≡ 308 ⋅ 52 ⋅ 556 ⋅ 117 ⋅ 235 mod 599
≡ 16016 ⋅ 556 ⋅ 117 ⋅ 235 mod 599 ≡ 442 ⋅ 556 ⋅ 117 ⋅ 235 mod 599
≡ 245752 ⋅ 117 ⋅ 235 mod 599 ≡ 162 ⋅ 117 ⋅ 235 mod 599
≡ 18954 ⋅ 235 mod 599 ≡ 385 ⋅ 235 mod 599
≡ 90475 mod 599 ≡ 26 mod 599

Es gilt also: 244¹¹⁸ ≡ 26 mod 599

Berechnung des größten gemeinsamen Teilers von 83 und 45

=>83	= 1⋅45 + 38
=>45	= 1⋅38 + 7
=>38	= 5⋅7 + 3
=>7	= 2⋅3 + 1
=>3	= 3⋅1 + 0

also gilt: ggt(83,45)=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= 7-2⋅3
3= 38-5⋅7	eingesetzt in die Zeile drüber:	1	= 1⋅7 -2⋅(38 -5⋅ 7) = 1⋅7 -2⋅38 +10⋅ 7) = -2⋅38 +11⋅ 7 (=1)
7= 45-1⋅38	eingesetzt in die Zeile drüber:	1	= -2⋅38 +11⋅(45 -1⋅ 38) = -2⋅38 +11⋅45 -11⋅ 38) = 11⋅45 -13⋅ 38 (=1)
38= 83-1⋅45	eingesetzt in die Zeile drüber:	1	= 11⋅45 -13⋅(83 -1⋅ 45) = 11⋅45 -13⋅83 +13⋅ 45) = -13⋅83 +24⋅ 45 (=1)

Es gilt also: ggt(83,45)=1 = -13⋅83 +24⋅45

oder wenn man -13⋅83 auf die linke Seite bringt:

1 +13⋅83 = +24⋅45

Es gilt also: 24⋅45 = 13⋅83 +1

Somit 24⋅45 = 1 mod 83

24 ist also das Inverse von 45 mod 83