Um längere Rechnungen zu vermeiden, rechnen wir:

(1793 + 3607) mod 9 ≡ (1793 mod 9 + 3607 mod 9) mod 9.

1793 mod 9 ≡ 2 mod 9 kann man relativ leicht bestimmen, weil ja 1793 = 1800-7 = 9 ⋅ 200 -7 = 9 ⋅ 200 - 9 + 2.

3607 mod 9 ≡ 7 mod 9 kann man relativ leicht bestimmen, weil ja 3607 = 3600+7 = 9 ⋅ 400 +7.

Somit gilt:

(1793 + 3607) mod 9 ≡ (2 + 7) mod 9 ≡ 9 mod 9 ≡ 0 mod 9.

Um längere Rechnungen zu vermeiden, rechnen wir:

(63 ⋅ 41) mod 7 ≡ (63 mod 7 ⋅ 41 mod 7) mod 7.

63 mod 7 ≡ 0 mod 7 kann man relativ leicht bestimmen, weil ja 63 = 63 + 0 = 9 ⋅ 7 + 0 ist.

41 mod 7 ≡ 6 mod 7 kann man relativ leicht bestimmen, weil ja 41 = 35 + 6 = 5 ⋅ 7 + 6 ist.

Somit gilt:

(63 ⋅ 41) mod 7 ≡ (0 ⋅ 6) mod 7 ≡ 0 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: 292¹=292

2: 292²=292¹⁺¹=292¹⋅292¹ ≡ 292⋅292=85264 ≡ 357 mod 431

4: 292⁴=292²⁺²=292²⋅292² ≡ 357⋅357=127449 ≡ 304 mod 431

8: 292⁸=292⁴⁺⁴=292⁴⋅292⁴ ≡ 304⋅304=92416 ≡ 182 mod 431

16: 292¹⁶=292⁸⁺⁸=292⁸⋅292⁸ ≡ 182⋅182=33124 ≡ 368 mod 431

32: 292³²=292¹⁶⁺¹⁶=292¹⁶⋅292¹⁶ ≡ 368⋅368=135424 ≡ 90 mod 431

64: 292⁶⁴=292³²⁺³²=292³²⋅292³² ≡ 90⋅90=8100 ≡ 342 mod 431

128: 292¹²⁸=292⁶⁴⁺⁶⁴=292⁶⁴⋅292⁶⁴ ≡ 342⋅342=116964 ≡ 163 mod 431

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

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

60 = 32+16+8+4

266⁶⁰

= 266^32+16+8+4

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

≡ 115 ⋅ 437 ⋅ 254 ⋅ 402 mod 461
≡ 50255 ⋅ 254 ⋅ 402 mod 461 ≡ 6 ⋅ 254 ⋅ 402 mod 461
≡ 1524 ⋅ 402 mod 461 ≡ 141 ⋅ 402 mod 461
≡ 56682 mod 461 ≡ 440 mod 461

Es gilt also: 266⁶⁰ ≡ 440 mod 461

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

=>83	= 1⋅43 + 40
=>43	= 1⋅40 + 3
=>40	= 13⋅3 + 1
=>3	= 3⋅1 + 0

also gilt: ggt(83,43)=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= 40-13⋅3
3= 43-1⋅40	eingesetzt in die Zeile drüber:	1	= 1⋅40 -13⋅(43 -1⋅ 40) = 1⋅40 -13⋅43 +13⋅ 40) = -13⋅43 +14⋅ 40 (=1)
40= 83-1⋅43	eingesetzt in die Zeile drüber:	1	= -13⋅43 +14⋅(83 -1⋅ 43) = -13⋅43 +14⋅83 -14⋅ 43) = 14⋅83 -27⋅ 43 (=1)

Es gilt also: ggt(83,43)=1 = 14⋅83 -27⋅43

oder wenn man 14⋅83 auf die linke Seite bringt:

1 -14⋅83 = -27⋅43

-27⋅43 = -14⋅83 + 1 |+83⋅43

-27⋅43 + 83⋅43 = -14⋅83 + 83⋅43 + 1

(-27 + 83) ⋅ 43 = (-14 + 43) ⋅ 83 + 1

56⋅43 = 29⋅83 + 1

Es gilt also: 56⋅43 = 29⋅83 +1

Somit 56⋅43 = 1 mod 83

56 ist also das Inverse von 43 mod 83