Um längere Rechnungen zu vermeiden, rechnen wir:

(2997 + 2404) mod 6 ≡ (2997 mod 6 + 2404 mod 6) mod 6.

2997 mod 6 ≡ 3 mod 6 kann man relativ leicht bestimmen, weil ja 2997 = 3000-3 = 6 ⋅ 500 -3 = 6 ⋅ 500 - 6 + 3.

2404 mod 6 ≡ 4 mod 6 kann man relativ leicht bestimmen, weil ja 2404 = 2400+4 = 6 ⋅ 400 +4.

Somit gilt:

(2997 + 2404) mod 6 ≡ (3 + 4) mod 6 ≡ 7 mod 6 ≡ 1 mod 6.

Um längere Rechnungen zu vermeiden, rechnen wir:

(73 ⋅ 80) mod 9 ≡ (73 mod 9 ⋅ 80 mod 9) mod 9.

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

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

Somit gilt:

(73 ⋅ 80) mod 9 ≡ (1 ⋅ 8) mod 9 ≡ 8 mod 9.

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

2: 261²=261¹⁺¹=261¹⋅261¹ ≡ 261⋅261=68121 ≡ 561 mod 563

4: 261⁴=261²⁺²=261²⋅261² ≡ 561⋅561=314721 ≡ 4 mod 563

8: 261⁸=261⁴⁺⁴=261⁴⋅261⁴ ≡ 4⋅4=16 ≡ 16 mod 563

16: 261¹⁶=261⁸⁺⁸=261⁸⋅261⁸ ≡ 16⋅16=256 ≡ 256 mod 563

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

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

183 = 128+32+16+4+2+1

287¹⁸³

= 287^{128+32+16+4+2+1}

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

≡ 414 ⋅ 113 ⋅ 144 ⋅ 39 ⋅ 380 ⋅ 287 mod 503
≡ 46782 ⋅ 144 ⋅ 39 ⋅ 380 ⋅ 287 mod 503 ≡ 3 ⋅ 144 ⋅ 39 ⋅ 380 ⋅ 287 mod 503
≡ 432 ⋅ 39 ⋅ 380 ⋅ 287 mod 503
≡ 16848 ⋅ 380 ⋅ 287 mod 503 ≡ 249 ⋅ 380 ⋅ 287 mod 503
≡ 94620 ⋅ 287 mod 503 ≡ 56 ⋅ 287 mod 503
≡ 16072 mod 503 ≡ 479 mod 503

Es gilt also: 287¹⁸³ ≡ 479 mod 503

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

=>71	= 1⋅59 + 12
=>59	= 4⋅12 + 11
=>12	= 1⋅11 + 1
=>11	= 11⋅1 + 0

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

Es gilt also: ggt(71,59)=1 = 5⋅71 -6⋅59

oder wenn man 5⋅71 auf die linke Seite bringt:

1 -5⋅71 = -6⋅59

-6⋅59 = -5⋅71 + 1 |+71⋅59

-6⋅59 + 71⋅59 = -5⋅71 + 71⋅59 + 1

(-6 + 71) ⋅ 59 = (-5 + 59) ⋅ 71 + 1

65⋅59 = 54⋅71 + 1

Es gilt also: 65⋅59 = 54⋅71 +1

Somit 65⋅59 = 1 mod 71

65 ist also das Inverse von 59 mod 71