Um längere Rechnungen zu vermeiden, rechnen wir:

(99 + 173) mod 9 ≡ (99 mod 9 + 173 mod 9) mod 9.

99 mod 9 ≡ 0 mod 9 kann man relativ leicht bestimmen, weil ja 99 = 90+9 = 9 ⋅ 10 +9.

173 mod 9 ≡ 2 mod 9 kann man relativ leicht bestimmen, weil ja 173 = 180-7 = 9 ⋅ 20 -7 = 9 ⋅ 20 - 9 + 2.

Somit gilt:

(99 + 173) mod 9 ≡ (0 + 2) mod 9 ≡ 2 mod 9.

Um längere Rechnungen zu vermeiden, rechnen wir:

(70 ⋅ 85) mod 8 ≡ (70 mod 8 ⋅ 85 mod 8) mod 8.

70 mod 8 ≡ 6 mod 8 kann man relativ leicht bestimmen, weil ja 70 = 64 + 6 = 8 ⋅ 8 + 6 ist.

85 mod 8 ≡ 5 mod 8 kann man relativ leicht bestimmen, weil ja 85 = 80 + 5 = 10 ⋅ 8 + 5 ist.

Somit gilt:

(70 ⋅ 85) mod 8 ≡ (6 ⋅ 5) mod 8 ≡ 30 mod 8 ≡ 6 mod 8.

Die 64 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: 581¹=581

2: 581²=581¹⁺¹=581¹⋅581¹ ≡ 581⋅581=337561 ≡ 438 mod 761

4: 581⁴=581²⁺²=581²⋅581² ≡ 438⋅438=191844 ≡ 72 mod 761

8: 581⁸=581⁴⁺⁴=581⁴⋅581⁴ ≡ 72⋅72=5184 ≡ 618 mod 761

16: 581¹⁶=581⁸⁺⁸=581⁸⋅581⁸ ≡ 618⋅618=381924 ≡ 663 mod 761

32: 581³²=581¹⁶⁺¹⁶=581¹⁶⋅581¹⁶ ≡ 663⋅663=439569 ≡ 472 mod 761

64: 581⁶⁴=581³²⁺³²=581³²⋅581³² ≡ 472⋅472=222784 ≡ 572 mod 761

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

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

255 = 128+64+32+16+8+4+2+1

431²⁵⁵

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

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

≡ 22 ⋅ 121 ⋅ 432 ⋅ 163 ⋅ 137 ⋅ 358 ⋅ 144 ⋅ 431 mod 443
≡ 2662 ⋅ 432 ⋅ 163 ⋅ 137 ⋅ 358 ⋅ 144 ⋅ 431 mod 443 ≡ 4 ⋅ 432 ⋅ 163 ⋅ 137 ⋅ 358 ⋅ 144 ⋅ 431 mod 443
≡ 1728 ⋅ 163 ⋅ 137 ⋅ 358 ⋅ 144 ⋅ 431 mod 443 ≡ 399 ⋅ 163 ⋅ 137 ⋅ 358 ⋅ 144 ⋅ 431 mod 443
≡ 65037 ⋅ 137 ⋅ 358 ⋅ 144 ⋅ 431 mod 443 ≡ 359 ⋅ 137 ⋅ 358 ⋅ 144 ⋅ 431 mod 443
≡ 49183 ⋅ 358 ⋅ 144 ⋅ 431 mod 443 ≡ 10 ⋅ 358 ⋅ 144 ⋅ 431 mod 443
≡ 3580 ⋅ 144 ⋅ 431 mod 443 ≡ 36 ⋅ 144 ⋅ 431 mod 443
≡ 5184 ⋅ 431 mod 443 ≡ 311 ⋅ 431 mod 443
≡ 134041 mod 443 ≡ 255 mod 443

Es gilt also: 431²⁵⁵ ≡ 255 mod 443

Berechnung des größten gemeinsamen Teilers von 101 und 38

=>101	= 2⋅38 + 25
=>38	= 1⋅25 + 13
=>25	= 1⋅13 + 12
=>13	= 1⋅12 + 1
=>12	= 12⋅1 + 0

also gilt: ggt(101,38)=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= 13-1⋅12
12= 25-1⋅13	eingesetzt in die Zeile drüber:	1	= 1⋅13 -1⋅(25 -1⋅ 13) = 1⋅13 -1⋅25 +1⋅ 13) = -1⋅25 +2⋅ 13 (=1)
13= 38-1⋅25	eingesetzt in die Zeile drüber:	1	= -1⋅25 +2⋅(38 -1⋅ 25) = -1⋅25 +2⋅38 -2⋅ 25) = 2⋅38 -3⋅ 25 (=1)
25= 101-2⋅38	eingesetzt in die Zeile drüber:	1	= 2⋅38 -3⋅(101 -2⋅ 38) = 2⋅38 -3⋅101 +6⋅ 38) = -3⋅101 +8⋅ 38 (=1)

Es gilt also: ggt(101,38)=1 = -3⋅101 +8⋅38

oder wenn man -3⋅101 auf die linke Seite bringt:

1 +3⋅101 = +8⋅38

Es gilt also: 8⋅38 = 3⋅101 +1

Somit 8⋅38 = 1 mod 101

8 ist also das Inverse von 38 mod 101