Um längere Rechnungen zu vermeiden, rechnen wir:

(3595 + 363) mod 9 ≡ (3595 mod 9 + 363 mod 9) mod 9.

3595 mod 9 ≡ 4 mod 9 kann man relativ leicht bestimmen, weil ja 3595 = 3600-5 = 9 ⋅ 400 -5 = 9 ⋅ 400 - 9 + 4.

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

Somit gilt:

(3595 + 363) mod 9 ≡ (4 + 3) mod 9 ≡ 7 mod 9.

Um längere Rechnungen zu vermeiden, rechnen wir:

(86 ⋅ 63) mod 7 ≡ (86 mod 7 ⋅ 63 mod 7) mod 7.

86 mod 7 ≡ 2 mod 7 kann man relativ leicht bestimmen, weil ja 86 = 84 + 2 = 12 ⋅ 7 + 2 ist.

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

Somit gilt:

(86 ⋅ 63) mod 7 ≡ (2 ⋅ 0) mod 7 ≡ 0 mod 7.

Die 32 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: 561¹=561

2: 561²=561¹⁺¹=561¹⋅561¹ ≡ 561⋅561=314721 ≡ 269 mod 619

4: 561⁴=561²⁺²=561²⋅561² ≡ 269⋅269=72361 ≡ 557 mod 619

8: 561⁸=561⁴⁺⁴=561⁴⋅561⁴ ≡ 557⋅557=310249 ≡ 130 mod 619

16: 561¹⁶=561⁸⁺⁸=561⁸⋅561⁸ ≡ 130⋅130=16900 ≡ 187 mod 619

32: 561³²=561¹⁶⁺¹⁶=561¹⁶⋅561¹⁶ ≡ 187⋅187=34969 ≡ 305 mod 619

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

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

247 = 128+64+32+16+4+2+1

200²⁴⁷

= 200^{128+64+32+16+4+2+1}

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

≡ 507 ⋅ 144 ⋅ 12 ⋅ 588 ⋅ 118 ⋅ 155 ⋅ 200 mod 613
≡ 73008 ⋅ 12 ⋅ 588 ⋅ 118 ⋅ 155 ⋅ 200 mod 613 ≡ 61 ⋅ 12 ⋅ 588 ⋅ 118 ⋅ 155 ⋅ 200 mod 613
≡ 732 ⋅ 588 ⋅ 118 ⋅ 155 ⋅ 200 mod 613 ≡ 119 ⋅ 588 ⋅ 118 ⋅ 155 ⋅ 200 mod 613
≡ 69972 ⋅ 118 ⋅ 155 ⋅ 200 mod 613 ≡ 90 ⋅ 118 ⋅ 155 ⋅ 200 mod 613
≡ 10620 ⋅ 155 ⋅ 200 mod 613 ≡ 199 ⋅ 155 ⋅ 200 mod 613
≡ 30845 ⋅ 200 mod 613 ≡ 195 ⋅ 200 mod 613
≡ 39000 mod 613 ≡ 381 mod 613

Es gilt also: 200²⁴⁷ ≡ 381 mod 613

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

=>73	= 1⋅51 + 22
=>51	= 2⋅22 + 7
=>22	= 3⋅7 + 1
=>7	= 7⋅1 + 0

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

Es gilt also: ggt(73,51)=1 = 7⋅73 -10⋅51

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

1 -7⋅73 = -10⋅51

-10⋅51 = -7⋅73 + 1 |+73⋅51

-10⋅51 + 73⋅51 = -7⋅73 + 73⋅51 + 1

(-10 + 73) ⋅ 51 = (-7 + 51) ⋅ 73 + 1

63⋅51 = 44⋅73 + 1

Es gilt also: 63⋅51 = 44⋅73 +1

Somit 63⋅51 = 1 mod 73

63 ist also das Inverse von 51 mod 73