Um längere Rechnungen zu vermeiden, rechnen wir:

(397 - 24003) mod 8 ≡ (397 mod 8 - 24003 mod 8) mod 8.

397 mod 8 ≡ 5 mod 8 kann man relativ leicht bestimmen, weil ja 397 = 400-3 = 8 ⋅ 50 -3 = 8 ⋅ 50 - 8 + 5.

24003 mod 8 ≡ 3 mod 8 kann man relativ leicht bestimmen, weil ja 24003 = 24000+3 = 8 ⋅ 3000 +3.

Somit gilt:

(397 - 24003) mod 8 ≡ (5 - 3) mod 8 ≡ 2 mod 8.

Um längere Rechnungen zu vermeiden, rechnen wir:

(84 ⋅ 37) mod 9 ≡ (84 mod 9 ⋅ 37 mod 9) mod 9.

84 mod 9 ≡ 3 mod 9 kann man relativ leicht bestimmen, weil ja 84 = 81 + 3 = 9 ⋅ 9 + 3 ist.

37 mod 9 ≡ 1 mod 9 kann man relativ leicht bestimmen, weil ja 37 = 36 + 1 = 4 ⋅ 9 + 1 ist.

Somit gilt:

(84 ⋅ 37) mod 9 ≡ (3 ⋅ 1) mod 9 ≡ 3 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: 293¹=293

2: 293²=293¹⁺¹=293¹⋅293¹ ≡ 293⋅293=85849 ≡ 780 mod 877

4: 293⁴=293²⁺²=293²⋅293² ≡ 780⋅780=608400 ≡ 639 mod 877

8: 293⁸=293⁴⁺⁴=293⁴⋅293⁴ ≡ 639⋅639=408321 ≡ 516 mod 877

16: 293¹⁶=293⁸⁺⁸=293⁸⋅293⁸ ≡ 516⋅516=266256 ≡ 525 mod 877

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

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

186 = 128+32+16+8+2

532¹⁸⁶

= 532^{128+32+16+8+2}

= 532¹²⁸⋅532³²⋅532¹⁶⋅532⁸⋅532²

≡ 165 ⋅ 358 ⋅ 426 ⋅ 320 ⋅ 693 mod 761
≡ 59070 ⋅ 426 ⋅ 320 ⋅ 693 mod 761 ≡ 473 ⋅ 426 ⋅ 320 ⋅ 693 mod 761
≡ 201498 ⋅ 320 ⋅ 693 mod 761 ≡ 594 ⋅ 320 ⋅ 693 mod 761
≡ 190080 ⋅ 693 mod 761 ≡ 591 ⋅ 693 mod 761
≡ 409563 mod 761 ≡ 145 mod 761

Es gilt also: 532¹⁸⁶ ≡ 145 mod 761

Berechnung des größten gemeinsamen Teilers von 79 und 41

=>79	= 1⋅41 + 38
=>41	= 1⋅38 + 3
=>38	= 12⋅3 + 2
=>3	= 1⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(79,41)=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= 38-12⋅3	eingesetzt in die Zeile drüber:	1	= 1⋅3 -1⋅(38 -12⋅ 3) = 1⋅3 -1⋅38 +12⋅ 3) = -1⋅38 +13⋅ 3 (=1)
3= 41-1⋅38	eingesetzt in die Zeile drüber:	1	= -1⋅38 +13⋅(41 -1⋅ 38) = -1⋅38 +13⋅41 -13⋅ 38) = 13⋅41 -14⋅ 38 (=1)
38= 79-1⋅41	eingesetzt in die Zeile drüber:	1	= 13⋅41 -14⋅(79 -1⋅ 41) = 13⋅41 -14⋅79 +14⋅ 41) = -14⋅79 +27⋅ 41 (=1)

Es gilt also: ggt(79,41)=1 = -14⋅79 +27⋅41

oder wenn man -14⋅79 auf die linke Seite bringt:

1 +14⋅79 = +27⋅41

Es gilt also: 27⋅41 = 14⋅79 +1

Somit 27⋅41 = 1 mod 79

27 ist also das Inverse von 41 mod 79