Um längere Rechnungen zu vermeiden, rechnen wir:

(898 + 15000) mod 3 ≡ (898 mod 3 + 15000 mod 3) mod 3.

898 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 898 = 900-2 = 3 ⋅ 300 -2 = 3 ⋅ 300 - 3 + 1.

15000 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 15000 = 15000+0 = 3 ⋅ 5000 +0.

Somit gilt:

(898 + 15000) mod 3 ≡ (1 + 0) mod 3 ≡ 1 mod 3.

Um längere Rechnungen zu vermeiden, rechnen wir:

(35 ⋅ 92) mod 6 ≡ (35 mod 6 ⋅ 92 mod 6) mod 6.

35 mod 6 ≡ 5 mod 6 kann man relativ leicht bestimmen, weil ja 35 = 30 + 5 = 5 ⋅ 6 + 5 ist.

92 mod 6 ≡ 2 mod 6 kann man relativ leicht bestimmen, weil ja 92 = 90 + 2 = 15 ⋅ 6 + 2 ist.

Somit gilt:

(35 ⋅ 92) mod 6 ≡ (5 ⋅ 2) mod 6 ≡ 10 mod 6 ≡ 4 mod 6.

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

2: 521²=521¹⁺¹=521¹⋅521¹ ≡ 521⋅521=271441 ≡ 129 mod 547

4: 521⁴=521²⁺²=521²⋅521² ≡ 129⋅129=16641 ≡ 231 mod 547

8: 521⁸=521⁴⁺⁴=521⁴⋅521⁴ ≡ 231⋅231=53361 ≡ 302 mod 547

16: 521¹⁶=521⁸⁺⁸=521⁸⋅521⁸ ≡ 302⋅302=91204 ≡ 402 mod 547

32: 521³²=521¹⁶⁺¹⁶=521¹⁶⋅521¹⁶ ≡ 402⋅402=161604 ≡ 239 mod 547

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

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

143 = 128+8+4+2+1

485¹⁴³

= 485^128+8+4+2+1

= 485¹²⁸⋅485⁸⋅485⁴⋅485²⋅485¹

≡ 370 ⋅ 499 ⋅ 226 ⋅ 665 ⋅ 485 mod 733
≡ 184630 ⋅ 226 ⋅ 665 ⋅ 485 mod 733 ≡ 647 ⋅ 226 ⋅ 665 ⋅ 485 mod 733
≡ 146222 ⋅ 665 ⋅ 485 mod 733 ≡ 355 ⋅ 665 ⋅ 485 mod 733
≡ 236075 ⋅ 485 mod 733 ≡ 49 ⋅ 485 mod 733
≡ 23765 mod 733 ≡ 309 mod 733

Es gilt also: 485¹⁴³ ≡ 309 mod 733

Berechnung des größten gemeinsamen Teilers von 101 und 77

=>101	= 1⋅77 + 24
=>77	= 3⋅24 + 5
=>24	= 4⋅5 + 4
=>5	= 1⋅4 + 1
=>4	= 4⋅1 + 0

also gilt: ggt(101,77)=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= 5-1⋅4
4= 24-4⋅5	eingesetzt in die Zeile drüber:	1	= 1⋅5 -1⋅(24 -4⋅ 5) = 1⋅5 -1⋅24 +4⋅ 5) = -1⋅24 +5⋅ 5 (=1)
5= 77-3⋅24	eingesetzt in die Zeile drüber:	1	= -1⋅24 +5⋅(77 -3⋅ 24) = -1⋅24 +5⋅77 -15⋅ 24) = 5⋅77 -16⋅ 24 (=1)
24= 101-1⋅77	eingesetzt in die Zeile drüber:	1	= 5⋅77 -16⋅(101 -1⋅ 77) = 5⋅77 -16⋅101 +16⋅ 77) = -16⋅101 +21⋅ 77 (=1)

Es gilt also: ggt(101,77)=1 = -16⋅101 +21⋅77

oder wenn man -16⋅101 auf die linke Seite bringt:

1 +16⋅101 = +21⋅77

Es gilt also: 21⋅77 = 16⋅101 +1

Somit 21⋅77 = 1 mod 101

21 ist also das Inverse von 77 mod 101