Um längere Rechnungen zu vermeiden, rechnen wir:

(12000 - 241) mod 6 ≡ (12000 mod 6 - 241 mod 6) mod 6.

12000 mod 6 ≡ 0 mod 6 kann man relativ leicht bestimmen, weil ja 12000 = 12000+0 = 6 ⋅ 2000 +0.

241 mod 6 ≡ 1 mod 6 kann man relativ leicht bestimmen, weil ja 241 = 240+1 = 6 ⋅ 40 +1.

Somit gilt:

(12000 - 241) mod 6 ≡ (0 - 1) mod 6 ≡ -1 mod 6 ≡ 5 mod 6.

Um längere Rechnungen zu vermeiden, rechnen wir:

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

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

82 mod 11 ≡ 5 mod 11 kann man relativ leicht bestimmen, weil ja 82 = 77 + 5 = 7 ⋅ 11 + 5 ist.

Somit gilt:

(68 ⋅ 82) mod 11 ≡ (2 ⋅ 5) mod 11 ≡ 10 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: 281¹=281

2: 281²=281¹⁺¹=281¹⋅281¹ ≡ 281⋅281=78961 ≡ 258 mod 373

4: 281⁴=281²⁺²=281²⋅281² ≡ 258⋅258=66564 ≡ 170 mod 373

8: 281⁸=281⁴⁺⁴=281⁴⋅281⁴ ≡ 170⋅170=28900 ≡ 179 mod 373

16: 281¹⁶=281⁸⁺⁸=281⁸⋅281⁸ ≡ 179⋅179=32041 ≡ 336 mod 373

32: 281³²=281¹⁶⁺¹⁶=281¹⁶⋅281¹⁶ ≡ 336⋅336=112896 ≡ 250 mod 373

64: 281⁶⁴=281³²⁺³²=281³²⋅281³² ≡ 250⋅250=62500 ≡ 209 mod 373

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

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

227 = 128+64+32+2+1

347²²⁷

= 347^{128+64+32+2+1}

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

≡ 259 ⋅ 178 ⋅ 75 ⋅ 156 ⋅ 347 mod 419
≡ 46102 ⋅ 75 ⋅ 156 ⋅ 347 mod 419 ≡ 12 ⋅ 75 ⋅ 156 ⋅ 347 mod 419
≡ 900 ⋅ 156 ⋅ 347 mod 419 ≡ 62 ⋅ 156 ⋅ 347 mod 419
≡ 9672 ⋅ 347 mod 419 ≡ 35 ⋅ 347 mod 419
≡ 12145 mod 419 ≡ 413 mod 419

Es gilt also: 347²²⁷ ≡ 413 mod 419

Berechnung des größten gemeinsamen Teilers von 67 und 32

=>67	= 2⋅32 + 3
=>32	= 10⋅3 + 2
=>3	= 1⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(67,32)=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= 32-10⋅3	eingesetzt in die Zeile drüber:	1	= 1⋅3 -1⋅(32 -10⋅ 3) = 1⋅3 -1⋅32 +10⋅ 3) = -1⋅32 +11⋅ 3 (=1)
3= 67-2⋅32	eingesetzt in die Zeile drüber:	1	= -1⋅32 +11⋅(67 -2⋅ 32) = -1⋅32 +11⋅67 -22⋅ 32) = 11⋅67 -23⋅ 32 (=1)

Es gilt also: ggt(67,32)=1 = 11⋅67 -23⋅32

oder wenn man 11⋅67 auf die linke Seite bringt:

1 -11⋅67 = -23⋅32

-23⋅32 = -11⋅67 + 1 |+67⋅32

-23⋅32 + 67⋅32 = -11⋅67 + 67⋅32 + 1

(-23 + 67) ⋅ 32 = (-11 + 32) ⋅ 67 + 1

44⋅32 = 21⋅67 + 1

Es gilt also: 44⋅32 = 21⋅67 +1

Somit 44⋅32 = 1 mod 67

44 ist also das Inverse von 32 mod 67