Um längere Rechnungen zu vermeiden, rechnen wir:

(50 - 98) mod 5 ≡ (50 mod 5 - 98 mod 5) mod 5.

50 mod 5 ≡ 0 mod 5 kann man relativ leicht bestimmen, weil ja 50 = 50+0 = 5 ⋅ 10 +0.

98 mod 5 ≡ 3 mod 5 kann man relativ leicht bestimmen, weil ja 98 = 90+8 = 5 ⋅ 18 +8.

Somit gilt:

(50 - 98) mod 5 ≡ (0 - 3) mod 5 ≡ -3 mod 5 ≡ 2 mod 5.

Um längere Rechnungen zu vermeiden, rechnen wir:

(56 ⋅ 19) mod 11 ≡ (56 mod 11 ⋅ 19 mod 11) mod 11.

56 mod 11 ≡ 1 mod 11 kann man relativ leicht bestimmen, weil ja 56 = 55 + 1 = 5 ⋅ 11 + 1 ist.

19 mod 11 ≡ 8 mod 11 kann man relativ leicht bestimmen, weil ja 19 = 11 + 8 = 1 ⋅ 11 + 8 ist.

Somit gilt:

(56 ⋅ 19) mod 11 ≡ (1 ⋅ 8) mod 11 ≡ 8 mod 11.

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

2: 235²=235¹⁺¹=235¹⋅235¹ ≡ 235⋅235=55225 ≡ 43 mod 541

4: 235⁴=235²⁺²=235²⋅235² ≡ 43⋅43=1849 ≡ 226 mod 541

8: 235⁸=235⁴⁺⁴=235⁴⋅235⁴ ≡ 226⋅226=51076 ≡ 222 mod 541

16: 235¹⁶=235⁸⁺⁸=235⁸⋅235⁸ ≡ 222⋅222=49284 ≡ 53 mod 541

32: 235³²=235¹⁶⁺¹⁶=235¹⁶⋅235¹⁶ ≡ 53⋅53=2809 ≡ 104 mod 541

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

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

189 = 128+32+16+8+4+1

516¹⁸⁹

= 516^{128+32+16+8+4+1}

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

≡ 368 ⋅ 556 ⋅ 390 ⋅ 762 ⋅ 258 ⋅ 516 mod 997
≡ 204608 ⋅ 390 ⋅ 762 ⋅ 258 ⋅ 516 mod 997 ≡ 223 ⋅ 390 ⋅ 762 ⋅ 258 ⋅ 516 mod 997
≡ 86970 ⋅ 762 ⋅ 258 ⋅ 516 mod 997 ≡ 231 ⋅ 762 ⋅ 258 ⋅ 516 mod 997
≡ 176022 ⋅ 258 ⋅ 516 mod 997 ≡ 550 ⋅ 258 ⋅ 516 mod 997
≡ 141900 ⋅ 516 mod 997 ≡ 326 ⋅ 516 mod 997
≡ 168216 mod 997 ≡ 720 mod 997

Es gilt also: 516¹⁸⁹ ≡ 720 mod 997

Berechnung des größten gemeinsamen Teilers von 53 und 48

=>53	= 1⋅48 + 5
=>48	= 9⋅5 + 3
=>5	= 1⋅3 + 2
=>3	= 1⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(53,48)=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= 3-1⋅2
2= 5-1⋅3	eingesetzt in die Zeile drüber:	1	= 1⋅3 -1⋅(5 -1⋅ 3) = 1⋅3 -1⋅5 +1⋅ 3) = -1⋅5 +2⋅ 3 (=1)
3= 48-9⋅5	eingesetzt in die Zeile drüber:	1	= -1⋅5 +2⋅(48 -9⋅ 5) = -1⋅5 +2⋅48 -18⋅ 5) = 2⋅48 -19⋅ 5 (=1)
5= 53-1⋅48	eingesetzt in die Zeile drüber:	1	= 2⋅48 -19⋅(53 -1⋅ 48) = 2⋅48 -19⋅53 +19⋅ 48) = -19⋅53 +21⋅ 48 (=1)

Es gilt also: ggt(53,48)=1 = -19⋅53 +21⋅48

oder wenn man -19⋅53 auf die linke Seite bringt:

1 +19⋅53 = +21⋅48

Es gilt also: 21⋅48 = 19⋅53 +1

Somit 21⋅48 = 1 mod 53

21 ist also das Inverse von 48 mod 53