Um längere Rechnungen zu vermeiden, rechnen wir:

(3193 + 15999) mod 8 ≡ (3193 mod 8 + 15999 mod 8) mod 8.

3193 mod 8 ≡ 1 mod 8 kann man relativ leicht bestimmen, weil ja 3193 = 3200-7 = 8 ⋅ 400 -7 = 8 ⋅ 400 - 8 + 1.

15999 mod 8 ≡ 7 mod 8 kann man relativ leicht bestimmen, weil ja 15999 = 15000+999 = 8 ⋅ 1875 +999.

Somit gilt:

(3193 + 15999) mod 8 ≡ (1 + 7) mod 8 ≡ 8 mod 8 ≡ 0 mod 8.

Um längere Rechnungen zu vermeiden, rechnen wir:

(41 ⋅ 92) mod 9 ≡ (41 mod 9 ⋅ 92 mod 9) mod 9.

41 mod 9 ≡ 5 mod 9 kann man relativ leicht bestimmen, weil ja 41 = 36 + 5 = 4 ⋅ 9 + 5 ist.

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

Somit gilt:

(41 ⋅ 92) mod 9 ≡ (5 ⋅ 2) mod 9 ≡ 10 mod 9 ≡ 1 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: 287¹=287

2: 287²=287¹⁺¹=287¹⋅287¹ ≡ 287⋅287=82369 ≡ 48 mod 431

4: 287⁴=287²⁺²=287²⋅287² ≡ 48⋅48=2304 ≡ 149 mod 431

8: 287⁸=287⁴⁺⁴=287⁴⋅287⁴ ≡ 149⋅149=22201 ≡ 220 mod 431

16: 287¹⁶=287⁸⁺⁸=287⁸⋅287⁸ ≡ 220⋅220=48400 ≡ 128 mod 431

32: 287³²=287¹⁶⁺¹⁶=287¹⁶⋅287¹⁶ ≡ 128⋅128=16384 ≡ 6 mod 431

64: 287⁶⁴=287³²⁺³²=287³²⋅287³² ≡ 6⋅6=36 ≡ 36 mod 431

128: 287¹²⁸=287⁶⁴⁺⁶⁴=287⁶⁴⋅287⁶⁴ ≡ 36⋅36=1296 ≡ 3 mod 431

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

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

246 = 128+64+32+16+4+2

139²⁴⁶

= 139^{128+64+32+16+4+2}

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

≡ 1 ⋅ 256 ⋅ 16 ⋅ 4 ⋅ 60 ⋅ 46 mod 257
≡ 256 ⋅ 16 ⋅ 4 ⋅ 60 ⋅ 46 mod 257
≡ 4096 ⋅ 4 ⋅ 60 ⋅ 46 mod 257 ≡ 241 ⋅ 4 ⋅ 60 ⋅ 46 mod 257
≡ 964 ⋅ 60 ⋅ 46 mod 257 ≡ 193 ⋅ 60 ⋅ 46 mod 257
≡ 11580 ⋅ 46 mod 257 ≡ 15 ⋅ 46 mod 257
≡ 690 mod 257 ≡ 176 mod 257

Es gilt also: 139²⁴⁶ ≡ 176 mod 257

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

=>73	= 3⋅23 + 4
=>23	= 5⋅4 + 3
=>4	= 1⋅3 + 1
=>3	= 3⋅1 + 0

also gilt: ggt(73,23)=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= 4-1⋅3
3= 23-5⋅4	eingesetzt in die Zeile drüber:	1	= 1⋅4 -1⋅(23 -5⋅ 4) = 1⋅4 -1⋅23 +5⋅ 4) = -1⋅23 +6⋅ 4 (=1)
4= 73-3⋅23	eingesetzt in die Zeile drüber:	1	= -1⋅23 +6⋅(73 -3⋅ 23) = -1⋅23 +6⋅73 -18⋅ 23) = 6⋅73 -19⋅ 23 (=1)

Es gilt also: ggt(73,23)=1 = 6⋅73 -19⋅23

oder wenn man 6⋅73 auf die linke Seite bringt:

1 -6⋅73 = -19⋅23

-19⋅23 = -6⋅73 + 1 |+73⋅23

-19⋅23 + 73⋅23 = -6⋅73 + 73⋅23 + 1

(-19 + 73) ⋅ 23 = (-6 + 23) ⋅ 73 + 1

54⋅23 = 17⋅73 + 1

Es gilt also: 54⋅23 = 17⋅73 +1

Somit 54⋅23 = 1 mod 73

54 ist also das Inverse von 23 mod 73