Um längere Rechnungen zu vermeiden, rechnen wir:

(323 + 1600) mod 8 ≡ (323 mod 8 + 1600 mod 8) mod 8.

323 mod 8 ≡ 3 mod 8 kann man relativ leicht bestimmen, weil ja 323 = 320+3 = 8 ⋅ 40 +3.

1600 mod 8 ≡ 0 mod 8 kann man relativ leicht bestimmen, weil ja 1600 = 1600+0 = 8 ⋅ 200 +0.

Somit gilt:

(323 + 1600) mod 8 ≡ (3 + 0) mod 8 ≡ 3 mod 8.

Um längere Rechnungen zu vermeiden, rechnen wir:

(68 ⋅ 99) mod 11 ≡ (68 mod 11 ⋅ 99 mod 11) mod 11.

68 mod 11 ≡ 2 mod 11 kann man relativ leicht bestimmen, weil ja 68 = 66 + 2 = 6 ⋅ 11 + 2 ist.

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

Somit gilt:

(68 ⋅ 99) mod 11 ≡ (2 ⋅ 0) mod 11 ≡ 0 mod 11.

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

2: 235²=235¹⁺¹=235¹⋅235¹ ≡ 235⋅235=55225 ≡ 373 mod 653

4: 235⁴=235²⁺²=235²⋅235² ≡ 373⋅373=139129 ≡ 40 mod 653

8: 235⁸=235⁴⁺⁴=235⁴⋅235⁴ ≡ 40⋅40=1600 ≡ 294 mod 653

16: 235¹⁶=235⁸⁺⁸=235⁸⋅235⁸ ≡ 294⋅294=86436 ≡ 240 mod 653

32: 235³²=235¹⁶⁺¹⁶=235¹⁶⋅235¹⁶ ≡ 240⋅240=57600 ≡ 136 mod 653

64: 235⁶⁴=235³²⁺³²=235³²⋅235³² ≡ 136⋅136=18496 ≡ 212 mod 653

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

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

248 = 128+64+32+16+8

82²⁴⁸

= 82^{128+64+32+16+8}

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

≡ 1 ⋅ 1 ⋅ 1 ⋅ 1 ⋅ 1 mod 269
≡ 1 ⋅ 1 ⋅ 1 ⋅ 1 mod 269
≡ 1 ⋅ 1 ⋅ 1 mod 269
≡ 1 ⋅ 1 mod 269
≡ 1 mod 269

Es gilt also: 82²⁴⁸ ≡ 1 mod 269

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

=>73	= 1⋅38 + 35
=>38	= 1⋅35 + 3
=>35	= 11⋅3 + 2
=>3	= 1⋅2 + 1
=>2	= 2⋅1 + 0

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

Es gilt also: ggt(73,38)=1 = -13⋅73 +25⋅38

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

1 +13⋅73 = +25⋅38

Es gilt also: 25⋅38 = 13⋅73 +1

Somit 25⋅38 = 1 mod 73

25 ist also das Inverse von 38 mod 73