Um längere Rechnungen zu vermeiden, rechnen wir:

(35999 + 8993) mod 9 ≡ (35999 mod 9 + 8993 mod 9) mod 9.

35999 mod 9 ≡ 8 mod 9 kann man relativ leicht bestimmen, weil ja 35999 = 36000-1 = 9 ⋅ 4000 -1 = 9 ⋅ 4000 - 9 + 8.

8993 mod 9 ≡ 2 mod 9 kann man relativ leicht bestimmen, weil ja 8993 = 9000-7 = 9 ⋅ 1000 -7 = 9 ⋅ 1000 - 9 + 2.

Somit gilt:

(35999 + 8993) mod 9 ≡ (8 + 2) mod 9 ≡ 10 mod 9 ≡ 1 mod 9.

Um längere Rechnungen zu vermeiden, rechnen wir:

(84 ⋅ 22) mod 5 ≡ (84 mod 5 ⋅ 22 mod 5) mod 5.

84 mod 5 ≡ 4 mod 5 kann man relativ leicht bestimmen, weil ja 84 = 80 + 4 = 16 ⋅ 5 + 4 ist.

22 mod 5 ≡ 2 mod 5 kann man relativ leicht bestimmen, weil ja 22 = 20 + 2 = 4 ⋅ 5 + 2 ist.

Somit gilt:

(84 ⋅ 22) mod 5 ≡ (4 ⋅ 2) mod 5 ≡ 8 mod 5 ≡ 3 mod 5.

Die 16 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: 646¹=646

2: 646²=646¹⁺¹=646¹⋅646¹ ≡ 646⋅646=417316 ≡ 209 mod 757

4: 646⁴=646²⁺²=646²⋅646² ≡ 209⋅209=43681 ≡ 532 mod 757

8: 646⁸=646⁴⁺⁴=646⁴⋅646⁴ ≡ 532⋅532=283024 ≡ 663 mod 757

16: 646¹⁶=646⁸⁺⁸=646⁸⋅646⁸ ≡ 663⋅663=439569 ≡ 509 mod 757

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

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

253 = 128+64+32+16+8+4+1

253²⁵³

= 253^{128+64+32+16+8+4+1}

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

≡ 153 ⋅ 22 ⋅ 118 ⋅ 214 ⋅ 144 ⋅ 319 ⋅ 253 mod 331
≡ 3366 ⋅ 118 ⋅ 214 ⋅ 144 ⋅ 319 ⋅ 253 mod 331 ≡ 56 ⋅ 118 ⋅ 214 ⋅ 144 ⋅ 319 ⋅ 253 mod 331
≡ 6608 ⋅ 214 ⋅ 144 ⋅ 319 ⋅ 253 mod 331 ≡ 319 ⋅ 214 ⋅ 144 ⋅ 319 ⋅ 253 mod 331
≡ 68266 ⋅ 144 ⋅ 319 ⋅ 253 mod 331 ≡ 80 ⋅ 144 ⋅ 319 ⋅ 253 mod 331
≡ 11520 ⋅ 319 ⋅ 253 mod 331 ≡ 266 ⋅ 319 ⋅ 253 mod 331
≡ 84854 ⋅ 253 mod 331 ≡ 118 ⋅ 253 mod 331
≡ 29854 mod 331 ≡ 64 mod 331

Es gilt also: 253²⁵³ ≡ 64 mod 331

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