Um längere Rechnungen zu vermeiden, rechnen wir:

(402 + 798) mod 8 ≡ (402 mod 8 + 798 mod 8) mod 8.

402 mod 8 ≡ 2 mod 8 kann man relativ leicht bestimmen, weil ja 402 = 400+2 = 8 ⋅ 50 +2.

798 mod 8 ≡ 6 mod 8 kann man relativ leicht bestimmen, weil ja 798 = 800-2 = 8 ⋅ 100 -2 = 8 ⋅ 100 - 8 + 6.

Somit gilt:

(402 + 798) mod 8 ≡ (2 + 6) mod 8 ≡ 8 mod 8 ≡ 0 mod 8.

Um längere Rechnungen zu vermeiden, rechnen wir:

(93 ⋅ 97) mod 4 ≡ (93 mod 4 ⋅ 97 mod 4) mod 4.

93 mod 4 ≡ 1 mod 4 kann man relativ leicht bestimmen, weil ja 93 = 92 + 1 = 23 ⋅ 4 + 1 ist.

97 mod 4 ≡ 1 mod 4 kann man relativ leicht bestimmen, weil ja 97 = 96 + 1 = 24 ⋅ 4 + 1 ist.

Somit gilt:

(93 ⋅ 97) mod 4 ≡ (1 ⋅ 1) mod 4 ≡ 1 mod 4.

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

2: 636²=636¹⁺¹=636¹⋅636¹ ≡ 636⋅636=404496 ≡ 284 mod 727

4: 636⁴=636²⁺²=636²⋅636² ≡ 284⋅284=80656 ≡ 686 mod 727

8: 636⁸=636⁴⁺⁴=636⁴⋅636⁴ ≡ 686⋅686=470596 ≡ 227 mod 727

16: 636¹⁶=636⁸⁺⁸=636⁸⋅636⁸ ≡ 227⋅227=51529 ≡ 639 mod 727

32: 636³²=636¹⁶⁺¹⁶=636¹⁶⋅636¹⁶ ≡ 639⋅639=408321 ≡ 474 mod 727

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

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

219 = 128+64+16+8+2+1

239²¹⁹

= 239^{128+64+16+8+2+1}

= 239¹²⁸⋅239⁶⁴⋅239¹⁶⋅239⁸⋅239²⋅239¹

≡ 521 ⋅ 419 ⋅ 11 ⋅ 445 ⋅ 233 ⋅ 239 mod 547
≡ 218299 ⋅ 11 ⋅ 445 ⋅ 233 ⋅ 239 mod 547 ≡ 46 ⋅ 11 ⋅ 445 ⋅ 233 ⋅ 239 mod 547
≡ 506 ⋅ 445 ⋅ 233 ⋅ 239 mod 547
≡ 225170 ⋅ 233 ⋅ 239 mod 547 ≡ 353 ⋅ 233 ⋅ 239 mod 547
≡ 82249 ⋅ 239 mod 547 ≡ 199 ⋅ 239 mod 547
≡ 47561 mod 547 ≡ 519 mod 547

Es gilt also: 239²¹⁹ ≡ 519 mod 547

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

=>71	= 1⋅46 + 25
=>46	= 1⋅25 + 21
=>25	= 1⋅21 + 4
=>21	= 5⋅4 + 1
=>4	= 4⋅1 + 0

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

Es gilt also: ggt(71,46)=1 = -11⋅71 +17⋅46

oder wenn man -11⋅71 auf die linke Seite bringt:

1 +11⋅71 = +17⋅46

Es gilt also: 17⋅46 = 11⋅71 +1

Somit 17⋅46 = 1 mod 71

17 ist also das Inverse von 46 mod 71