Um längere Rechnungen zu vermeiden, rechnen wir:

(49 - 10002) mod 5 ≡ (49 mod 5 - 10002 mod 5) mod 5.

49 mod 5 ≡ 4 mod 5 kann man relativ leicht bestimmen, weil ja 49 = 40+9 = 5 ⋅ 8 +9.

10002 mod 5 ≡ 2 mod 5 kann man relativ leicht bestimmen, weil ja 10002 = 10000+2 = 5 ⋅ 2000 +2.

Somit gilt:

(49 - 10002) mod 5 ≡ (4 - 2) mod 5 ≡ 2 mod 5.

Um längere Rechnungen zu vermeiden, rechnen wir:

(22 ⋅ 25) mod 4 ≡ (22 mod 4 ⋅ 25 mod 4) mod 4.

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

25 mod 4 ≡ 1 mod 4 kann man relativ leicht bestimmen, weil ja 25 = 24 + 1 = 6 ⋅ 4 + 1 ist.

Somit gilt:

(22 ⋅ 25) mod 4 ≡ (2 ⋅ 1) mod 4 ≡ 2 mod 4.

Die 128 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: 475¹=475

2: 475²=475¹⁺¹=475¹⋅475¹ ≡ 475⋅475=225625 ≡ 726 mod 941

4: 475⁴=475²⁺²=475²⋅475² ≡ 726⋅726=527076 ≡ 116 mod 941

8: 475⁸=475⁴⁺⁴=475⁴⋅475⁴ ≡ 116⋅116=13456 ≡ 282 mod 941

16: 475¹⁶=475⁸⁺⁸=475⁸⋅475⁸ ≡ 282⋅282=79524 ≡ 480 mod 941

32: 475³²=475¹⁶⁺¹⁶=475¹⁶⋅475¹⁶ ≡ 480⋅480=230400 ≡ 796 mod 941

64: 475⁶⁴=475³²⁺³²=475³²⋅475³² ≡ 796⋅796=633616 ≡ 323 mod 941

128: 475¹²⁸=475⁶⁴⁺⁶⁴=475⁶⁴⋅475⁶⁴ ≡ 323⋅323=104329 ≡ 819 mod 941

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

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

199 = 128+64+4+2+1

631¹⁹⁹

= 631^128+64+4+2+1

= 631¹²⁸⋅631⁶⁴⋅631⁴⋅631²⋅631¹

≡ 150 ⋅ 582 ⋅ 491 ⋅ 66 ⋅ 631 mod 773
≡ 87300 ⋅ 491 ⋅ 66 ⋅ 631 mod 773 ≡ 724 ⋅ 491 ⋅ 66 ⋅ 631 mod 773
≡ 355484 ⋅ 66 ⋅ 631 mod 773 ≡ 677 ⋅ 66 ⋅ 631 mod 773
≡ 44682 ⋅ 631 mod 773 ≡ 621 ⋅ 631 mod 773
≡ 391851 mod 773 ≡ 713 mod 773

Es gilt also: 631¹⁹⁹ ≡ 713 mod 773

Berechnung des größten gemeinsamen Teilers von 83 und 39

=>83	= 2⋅39 + 5
=>39	= 7⋅5 + 4
=>5	= 1⋅4 + 1
=>4	= 4⋅1 + 0

also gilt: ggt(83,39)=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= 5-1⋅4
4= 39-7⋅5	eingesetzt in die Zeile drüber:	1	= 1⋅5 -1⋅(39 -7⋅ 5) = 1⋅5 -1⋅39 +7⋅ 5) = -1⋅39 +8⋅ 5 (=1)
5= 83-2⋅39	eingesetzt in die Zeile drüber:	1	= -1⋅39 +8⋅(83 -2⋅ 39) = -1⋅39 +8⋅83 -16⋅ 39) = 8⋅83 -17⋅ 39 (=1)

Es gilt also: ggt(83,39)=1 = 8⋅83 -17⋅39

oder wenn man 8⋅83 auf die linke Seite bringt:

1 -8⋅83 = -17⋅39

-17⋅39 = -8⋅83 + 1 |+83⋅39

-17⋅39 + 83⋅39 = -8⋅83 + 83⋅39 + 1

(-17 + 83) ⋅ 39 = (-8 + 39) ⋅ 83 + 1

66⋅39 = 31⋅83 + 1

Es gilt also: 66⋅39 = 31⋅83 +1

Somit 66⋅39 = 1 mod 83

66 ist also das Inverse von 39 mod 83