Um längere Rechnungen zu vermeiden, rechnen wir:

(203 - 40) mod 4 ≡ (203 mod 4 - 40 mod 4) mod 4.

203 mod 4 ≡ 3 mod 4 kann man relativ leicht bestimmen, weil ja 203 = 200+3 = 4 ⋅ 50 +3.

40 mod 4 ≡ 0 mod 4 kann man relativ leicht bestimmen, weil ja 40 = 40+0 = 4 ⋅ 10 +0.

Somit gilt:

(203 - 40) mod 4 ≡ (3 - 0) mod 4 ≡ 3 mod 4.

Um längere Rechnungen zu vermeiden, rechnen wir:

(74 ⋅ 100) mod 8 ≡ (74 mod 8 ⋅ 100 mod 8) mod 8.

74 mod 8 ≡ 2 mod 8 kann man relativ leicht bestimmen, weil ja 74 = 72 + 2 = 9 ⋅ 8 + 2 ist.

100 mod 8 ≡ 4 mod 8 kann man relativ leicht bestimmen, weil ja 100 = 96 + 4 = 12 ⋅ 8 + 4 ist.

Somit gilt:

(74 ⋅ 100) mod 8 ≡ (2 ⋅ 4) mod 8 ≡ 8 mod 8 ≡ 0 mod 8.

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

2: 291²=291¹⁺¹=291¹⋅291¹ ≡ 291⋅291=84681 ≡ 4 mod 293

4: 291⁴=291²⁺²=291²⋅291² ≡ 4⋅4=16 ≡ 16 mod 293

8: 291⁸=291⁴⁺⁴=291⁴⋅291⁴ ≡ 16⋅16=256 ≡ 256 mod 293

16: 291¹⁶=291⁸⁺⁸=291⁸⋅291⁸ ≡ 256⋅256=65536 ≡ 197 mod 293

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

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

222 = 128+64+16+8+4+2

726²²²

= 726^{128+64+16+8+4+2}

= 726¹²⁸⋅726⁶⁴⋅726¹⁶⋅726⁸⋅726⁴⋅726²

≡ 90 ⋅ 536 ⋅ 666 ⋅ 644 ⋅ 260 ⋅ 238 mod 881
≡ 48240 ⋅ 666 ⋅ 644 ⋅ 260 ⋅ 238 mod 881 ≡ 666 ⋅ 666 ⋅ 644 ⋅ 260 ⋅ 238 mod 881
≡ 443556 ⋅ 644 ⋅ 260 ⋅ 238 mod 881 ≡ 413 ⋅ 644 ⋅ 260 ⋅ 238 mod 881
≡ 265972 ⋅ 260 ⋅ 238 mod 881 ≡ 791 ⋅ 260 ⋅ 238 mod 881
≡ 205660 ⋅ 238 mod 881 ≡ 387 ⋅ 238 mod 881
≡ 92106 mod 881 ≡ 482 mod 881

Es gilt also: 726²²² ≡ 482 mod 881

Berechnung des größten gemeinsamen Teilers von 83 und 55

=>83	= 1⋅55 + 28
=>55	= 1⋅28 + 27
=>28	= 1⋅27 + 1
=>27	= 27⋅1 + 0

also gilt: ggt(83,55)=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= 28-1⋅27
27= 55-1⋅28	eingesetzt in die Zeile drüber:	1	= 1⋅28 -1⋅(55 -1⋅ 28) = 1⋅28 -1⋅55 +1⋅ 28) = -1⋅55 +2⋅ 28 (=1)
28= 83-1⋅55	eingesetzt in die Zeile drüber:	1	= -1⋅55 +2⋅(83 -1⋅ 55) = -1⋅55 +2⋅83 -2⋅ 55) = 2⋅83 -3⋅ 55 (=1)

Es gilt also: ggt(83,55)=1 = 2⋅83 -3⋅55

oder wenn man 2⋅83 auf die linke Seite bringt:

1 -2⋅83 = -3⋅55

-3⋅55 = -2⋅83 + 1 |+83⋅55

-3⋅55 + 83⋅55 = -2⋅83 + 83⋅55 + 1

(-3 + 83) ⋅ 55 = (-2 + 55) ⋅ 83 + 1

80⋅55 = 53⋅83 + 1

Es gilt also: 80⋅55 = 53⋅83 +1

Somit 80⋅55 = 1 mod 83

80 ist also das Inverse von 55 mod 83