Um längere Rechnungen zu vermeiden, rechnen wir:

(4001 + 803) mod 4 ≡ (4001 mod 4 + 803 mod 4) mod 4.

4001 mod 4 ≡ 1 mod 4 kann man relativ leicht bestimmen, weil ja 4001 = 4000+1 = 4 ⋅ 1000 +1.

803 mod 4 ≡ 3 mod 4 kann man relativ leicht bestimmen, weil ja 803 = 800+3 = 4 ⋅ 200 +3.

Somit gilt:

(4001 + 803) mod 4 ≡ (1 + 3) mod 4 ≡ 4 mod 4 ≡ 0 mod 4.

Um längere Rechnungen zu vermeiden, rechnen wir:

(72 ⋅ 90) mod 8 ≡ (72 mod 8 ⋅ 90 mod 8) mod 8.

72 mod 8 ≡ 0 mod 8 kann man relativ leicht bestimmen, weil ja 72 = 72 + 0 = 9 ⋅ 8 + 0 ist.

90 mod 8 ≡ 2 mod 8 kann man relativ leicht bestimmen, weil ja 90 = 88 + 2 = 11 ⋅ 8 + 2 ist.

Somit gilt:

(72 ⋅ 90) mod 8 ≡ (0 ⋅ 2) mod 8 ≡ 0 mod 8.

Die 64 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: 270¹=270

2: 270²=270¹⁺¹=270¹⋅270¹ ≡ 270⋅270=72900 ≡ 62 mod 461

4: 270⁴=270²⁺²=270²⋅270² ≡ 62⋅62=3844 ≡ 156 mod 461

8: 270⁸=270⁴⁺⁴=270⁴⋅270⁴ ≡ 156⋅156=24336 ≡ 364 mod 461

16: 270¹⁶=270⁸⁺⁸=270⁸⋅270⁸ ≡ 364⋅364=132496 ≡ 189 mod 461

32: 270³²=270¹⁶⁺¹⁶=270¹⁶⋅270¹⁶ ≡ 189⋅189=35721 ≡ 224 mod 461

64: 270⁶⁴=270³²⁺³²=270³²⋅270³² ≡ 224⋅224=50176 ≡ 388 mod 461

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

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

127 = 64+32+16+8+4+2+1

632¹²⁷

= 632^{64+32+16+8+4+2+1}

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

≡ 182 ⋅ 651 ⋅ 75 ⋅ 342 ⋅ 504 ⋅ 675 ⋅ 632 mod 829
≡ 118482 ⋅ 75 ⋅ 342 ⋅ 504 ⋅ 675 ⋅ 632 mod 829 ≡ 764 ⋅ 75 ⋅ 342 ⋅ 504 ⋅ 675 ⋅ 632 mod 829
≡ 57300 ⋅ 342 ⋅ 504 ⋅ 675 ⋅ 632 mod 829 ≡ 99 ⋅ 342 ⋅ 504 ⋅ 675 ⋅ 632 mod 829
≡ 33858 ⋅ 504 ⋅ 675 ⋅ 632 mod 829 ≡ 698 ⋅ 504 ⋅ 675 ⋅ 632 mod 829
≡ 351792 ⋅ 675 ⋅ 632 mod 829 ≡ 296 ⋅ 675 ⋅ 632 mod 829
≡ 199800 ⋅ 632 mod 829 ≡ 11 ⋅ 632 mod 829
≡ 6952 mod 829 ≡ 320 mod 829

Es gilt also: 632¹²⁷ ≡ 320 mod 829

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

=>101	= 1⋅52 + 49
=>52	= 1⋅49 + 3
=>49	= 16⋅3 + 1
=>3	= 3⋅1 + 0

also gilt: ggt(101,52)=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= 49-16⋅3
3= 52-1⋅49	eingesetzt in die Zeile drüber:	1	= 1⋅49 -16⋅(52 -1⋅ 49) = 1⋅49 -16⋅52 +16⋅ 49) = -16⋅52 +17⋅ 49 (=1)
49= 101-1⋅52	eingesetzt in die Zeile drüber:	1	= -16⋅52 +17⋅(101 -1⋅ 52) = -16⋅52 +17⋅101 -17⋅ 52) = 17⋅101 -33⋅ 52 (=1)

Es gilt also: ggt(101,52)=1 = 17⋅101 -33⋅52

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

1 -17⋅101 = -33⋅52

-33⋅52 = -17⋅101 + 1 |+101⋅52

-33⋅52 + 101⋅52 = -17⋅101 + 101⋅52 + 1

(-33 + 101) ⋅ 52 = (-17 + 52) ⋅ 101 + 1

68⋅52 = 35⋅101 + 1

Es gilt also: 68⋅52 = 35⋅101 +1

Somit 68⋅52 = 1 mod 101

68 ist also das Inverse von 52 mod 101