Um längere Rechnungen zu vermeiden, rechnen wir:

(6003 + 150) mod 3 ≡ (6003 mod 3 + 150 mod 3) mod 3.

6003 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 6003 = 6000+3 = 3 ⋅ 2000 +3.

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

Somit gilt:

(6003 + 150) mod 3 ≡ (0 + 0) mod 3 ≡ 0 mod 3.

Um längere Rechnungen zu vermeiden, rechnen wir:

(96 ⋅ 82) mod 3 ≡ (96 mod 3 ⋅ 82 mod 3) mod 3.

96 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 96 = 96 + 0 = 32 ⋅ 3 + 0 ist.

82 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 82 = 81 + 1 = 27 ⋅ 3 + 1 ist.

Somit gilt:

(96 ⋅ 82) mod 3 ≡ (0 ⋅ 1) mod 3 ≡ 0 mod 3.

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

2: 786²=786¹⁺¹=786¹⋅786¹ ≡ 786⋅786=617796 ≡ 11 mod 929

4: 786⁴=786²⁺²=786²⋅786² ≡ 11⋅11=121 ≡ 121 mod 929

8: 786⁸=786⁴⁺⁴=786⁴⋅786⁴ ≡ 121⋅121=14641 ≡ 706 mod 929

16: 786¹⁶=786⁸⁺⁸=786⁸⋅786⁸ ≡ 706⋅706=498436 ≡ 492 mod 929

32: 786³²=786¹⁶⁺¹⁶=786¹⁶⋅786¹⁶ ≡ 492⋅492=242064 ≡ 524 mod 929

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

376¹⁸⁹

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

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

≡ 562 ⋅ 493 ⋅ 317 ⋅ 433 ⋅ 459 ⋅ 376 mod 641
≡ 277066 ⋅ 317 ⋅ 433 ⋅ 459 ⋅ 376 mod 641 ≡ 154 ⋅ 317 ⋅ 433 ⋅ 459 ⋅ 376 mod 641
≡ 48818 ⋅ 433 ⋅ 459 ⋅ 376 mod 641 ≡ 102 ⋅ 433 ⋅ 459 ⋅ 376 mod 641
≡ 44166 ⋅ 459 ⋅ 376 mod 641 ≡ 578 ⋅ 459 ⋅ 376 mod 641
≡ 265302 ⋅ 376 mod 641 ≡ 569 ⋅ 376 mod 641
≡ 213944 mod 641 ≡ 491 mod 641

Es gilt also: 376¹⁸⁹ ≡ 491 mod 641

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

=>101	= 2⋅36 + 29
=>36	= 1⋅29 + 7
=>29	= 4⋅7 + 1
=>7	= 7⋅1 + 0

also gilt: ggt(101,36)=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= 29-4⋅7
7= 36-1⋅29	eingesetzt in die Zeile drüber:	1	= 1⋅29 -4⋅(36 -1⋅ 29) = 1⋅29 -4⋅36 +4⋅ 29) = -4⋅36 +5⋅ 29 (=1)
29= 101-2⋅36	eingesetzt in die Zeile drüber:	1	= -4⋅36 +5⋅(101 -2⋅ 36) = -4⋅36 +5⋅101 -10⋅ 36) = 5⋅101 -14⋅ 36 (=1)

Es gilt also: ggt(101,36)=1 = 5⋅101 -14⋅36

oder wenn man 5⋅101 auf die linke Seite bringt:

1 -5⋅101 = -14⋅36

-14⋅36 = -5⋅101 + 1 |+101⋅36

-14⋅36 + 101⋅36 = -5⋅101 + 101⋅36 + 1

(-14 + 101) ⋅ 36 = (-5 + 36) ⋅ 101 + 1

87⋅36 = 31⋅101 + 1

Es gilt also: 87⋅36 = 31⋅101 +1

Somit 87⋅36 = 1 mod 101

87 ist also das Inverse von 36 mod 101