Um längere Rechnungen zu vermeiden, rechnen wir:

(360 - 18007) mod 9 ≡ (360 mod 9 - 18007 mod 9) mod 9.

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

18007 mod 9 ≡ 7 mod 9 kann man relativ leicht bestimmen, weil ja 18007 = 18000+7 = 9 ⋅ 2000 +7.

Somit gilt:

(360 - 18007) mod 9 ≡ (0 - 7) mod 9 ≡ -7 mod 9 ≡ 2 mod 9.

Um längere Rechnungen zu vermeiden, rechnen wir:

(95 ⋅ 33) mod 11 ≡ (95 mod 11 ⋅ 33 mod 11) mod 11.

95 mod 11 ≡ 7 mod 11 kann man relativ leicht bestimmen, weil ja 95 = 88 + 7 = 8 ⋅ 11 + 7 ist.

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

Somit gilt:

(95 ⋅ 33) mod 11 ≡ (7 ⋅ 0) mod 11 ≡ 0 mod 11.

Die 8 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: 804¹=804

2: 804²=804¹⁺¹=804¹⋅804¹ ≡ 804⋅804=646416 ≡ 289 mod 821

4: 804⁴=804²⁺²=804²⋅804² ≡ 289⋅289=83521 ≡ 600 mod 821

8: 804⁸=804⁴⁺⁴=804⁴⋅804⁴ ≡ 600⋅600=360000 ≡ 402 mod 821

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

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

187 = 128+32+16+8+2+1

310¹⁸⁷

= 310^{128+32+16+8+2+1}

= 310¹²⁸⋅310³²⋅310¹⁶⋅310⁸⋅310²⋅310¹

≡ 117 ⋅ 256 ⋅ 16 ⋅ 517 ⋅ 236 ⋅ 310 mod 521
≡ 29952 ⋅ 16 ⋅ 517 ⋅ 236 ⋅ 310 mod 521 ≡ 255 ⋅ 16 ⋅ 517 ⋅ 236 ⋅ 310 mod 521
≡ 4080 ⋅ 517 ⋅ 236 ⋅ 310 mod 521 ≡ 433 ⋅ 517 ⋅ 236 ⋅ 310 mod 521
≡ 223861 ⋅ 236 ⋅ 310 mod 521 ≡ 352 ⋅ 236 ⋅ 310 mod 521
≡ 83072 ⋅ 310 mod 521 ≡ 233 ⋅ 310 mod 521
≡ 72230 mod 521 ≡ 332 mod 521

Es gilt also: 310¹⁸⁷ ≡ 332 mod 521

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

=>83	= 1⋅71 + 12
=>71	= 5⋅12 + 11
=>12	= 1⋅11 + 1
=>11	= 11⋅1 + 0

also gilt: ggt(83,71)=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= 12-1⋅11
11= 71-5⋅12	eingesetzt in die Zeile drüber:	1	= 1⋅12 -1⋅(71 -5⋅ 12) = 1⋅12 -1⋅71 +5⋅ 12) = -1⋅71 +6⋅ 12 (=1)
12= 83-1⋅71	eingesetzt in die Zeile drüber:	1	= -1⋅71 +6⋅(83 -1⋅ 71) = -1⋅71 +6⋅83 -6⋅ 71) = 6⋅83 -7⋅ 71 (=1)

Es gilt also: ggt(83,71)=1 = 6⋅83 -7⋅71

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

1 -6⋅83 = -7⋅71

-7⋅71 = -6⋅83 + 1 |+83⋅71

-7⋅71 + 83⋅71 = -6⋅83 + 83⋅71 + 1

(-7 + 83) ⋅ 71 = (-6 + 71) ⋅ 83 + 1

76⋅71 = 65⋅83 + 1

Es gilt also: 76⋅71 = 65⋅83 +1

Somit 76⋅71 = 1 mod 83

76 ist also das Inverse von 71 mod 83