Um längere Rechnungen zu vermeiden, rechnen wir:

(1999 - 2505) mod 5 ≡ (1999 mod 5 - 2505 mod 5) mod 5.

1999 mod 5 ≡ 4 mod 5 kann man relativ leicht bestimmen, weil ja 1999 = 1900+99 = 5 ⋅ 380 +99.

2505 mod 5 ≡ 0 mod 5 kann man relativ leicht bestimmen, weil ja 2505 = 2500+5 = 5 ⋅ 500 +5.

Somit gilt:

(1999 - 2505) mod 5 ≡ (4 - 0) mod 5 ≡ 4 mod 5.

Um längere Rechnungen zu vermeiden, rechnen wir:

(35 ⋅ 25) mod 10 ≡ (35 mod 10 ⋅ 25 mod 10) mod 10.

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

25 mod 10 ≡ 5 mod 10 kann man relativ leicht bestimmen, weil ja 25 = 20 + 5 = 2 ⋅ 10 + 5 ist.

Somit gilt:

(35 ⋅ 25) mod 10 ≡ (5 ⋅ 5) mod 10 ≡ 25 mod 10 ≡ 5 mod 10.

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

2: 569²=569¹⁺¹=569¹⋅569¹ ≡ 569⋅569=323761 ≡ 508 mod 733

4: 569⁴=569²⁺²=569²⋅569² ≡ 508⋅508=258064 ≡ 48 mod 733

8: 569⁸=569⁴⁺⁴=569⁴⋅569⁴ ≡ 48⋅48=2304 ≡ 105 mod 733

16: 569¹⁶=569⁸⁺⁸=569⁸⋅569⁸ ≡ 105⋅105=11025 ≡ 30 mod 733

32: 569³²=569¹⁶⁺¹⁶=569¹⁶⋅569¹⁶ ≡ 30⋅30=900 ≡ 167 mod 733

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

213¹⁸⁹

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

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

≡ 186 ⋅ 304 ⋅ 189 ⋅ 239 ⋅ 153 ⋅ 213 mod 331
≡ 56544 ⋅ 189 ⋅ 239 ⋅ 153 ⋅ 213 mod 331 ≡ 274 ⋅ 189 ⋅ 239 ⋅ 153 ⋅ 213 mod 331
≡ 51786 ⋅ 239 ⋅ 153 ⋅ 213 mod 331 ≡ 150 ⋅ 239 ⋅ 153 ⋅ 213 mod 331
≡ 35850 ⋅ 153 ⋅ 213 mod 331 ≡ 102 ⋅ 153 ⋅ 213 mod 331
≡ 15606 ⋅ 213 mod 331 ≡ 49 ⋅ 213 mod 331
≡ 10437 mod 331 ≡ 176 mod 331

Es gilt also: 213¹⁸⁹ ≡ 176 mod 331

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

=>71	= 1⋅55 + 16
=>55	= 3⋅16 + 7
=>16	= 2⋅7 + 2
=>7	= 3⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(71,55)=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= 7-3⋅2
2= 16-2⋅7	eingesetzt in die Zeile drüber:	1	= 1⋅7 -3⋅(16 -2⋅ 7) = 1⋅7 -3⋅16 +6⋅ 7) = -3⋅16 +7⋅ 7 (=1)
7= 55-3⋅16	eingesetzt in die Zeile drüber:	1	= -3⋅16 +7⋅(55 -3⋅ 16) = -3⋅16 +7⋅55 -21⋅ 16) = 7⋅55 -24⋅ 16 (=1)
16= 71-1⋅55	eingesetzt in die Zeile drüber:	1	= 7⋅55 -24⋅(71 -1⋅ 55) = 7⋅55 -24⋅71 +24⋅ 55) = -24⋅71 +31⋅ 55 (=1)

Es gilt also: ggt(71,55)=1 = -24⋅71 +31⋅55

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

1 +24⋅71 = +31⋅55

Es gilt also: 31⋅55 = 24⋅71 +1

Somit 31⋅55 = 1 mod 71

31 ist also das Inverse von 55 mod 71