Um längere Rechnungen zu vermeiden, rechnen wir:

(3496 - 2803) mod 7 ≡ (3496 mod 7 - 2803 mod 7) mod 7.

3496 mod 7 ≡ 3 mod 7 kann man relativ leicht bestimmen, weil ja 3496 = 3500-4 = 7 ⋅ 500 -4 = 7 ⋅ 500 - 7 + 3.

2803 mod 7 ≡ 3 mod 7 kann man relativ leicht bestimmen, weil ja 2803 = 2800+3 = 7 ⋅ 400 +3.

Somit gilt:

(3496 - 2803) mod 7 ≡ (3 - 3) mod 7 ≡ 0 mod 7.

Um längere Rechnungen zu vermeiden, rechnen wir:

(42 ⋅ 71) mod 7 ≡ (42 mod 7 ⋅ 71 mod 7) mod 7.

42 mod 7 ≡ 0 mod 7 kann man relativ leicht bestimmen, weil ja 42 = 42 + 0 = 6 ⋅ 7 + 0 ist.

71 mod 7 ≡ 1 mod 7 kann man relativ leicht bestimmen, weil ja 71 = 70 + 1 = 10 ⋅ 7 + 1 ist.

Somit gilt:

(42 ⋅ 71) mod 7 ≡ (0 ⋅ 1) mod 7 ≡ 0 mod 7.

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

2: 172²=172¹⁺¹=172¹⋅172¹ ≡ 172⋅172=29584 ≡ 346 mod 443

4: 172⁴=172²⁺²=172²⋅172² ≡ 346⋅346=119716 ≡ 106 mod 443

8: 172⁸=172⁴⁺⁴=172⁴⋅172⁴ ≡ 106⋅106=11236 ≡ 161 mod 443

16: 172¹⁶=172⁸⁺⁸=172⁸⋅172⁸ ≡ 161⋅161=25921 ≡ 227 mod 443

32: 172³²=172¹⁶⁺¹⁶=172¹⁶⋅172¹⁶ ≡ 227⋅227=51529 ≡ 141 mod 443

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

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

222 = 128+64+16+8+4+2

842²²²

= 842^{128+64+16+8+4+2}

= 842¹²⁸⋅842⁶⁴⋅842¹⁶⋅842⁸⋅842⁴⋅842²

≡ 270 ⋅ 462 ⋅ 778 ⋅ 312 ⋅ 530 ⋅ 206 mod 911
≡ 124740 ⋅ 778 ⋅ 312 ⋅ 530 ⋅ 206 mod 911 ≡ 844 ⋅ 778 ⋅ 312 ⋅ 530 ⋅ 206 mod 911
≡ 656632 ⋅ 312 ⋅ 530 ⋅ 206 mod 911 ≡ 712 ⋅ 312 ⋅ 530 ⋅ 206 mod 911
≡ 222144 ⋅ 530 ⋅ 206 mod 911 ≡ 771 ⋅ 530 ⋅ 206 mod 911
≡ 408630 ⋅ 206 mod 911 ≡ 502 ⋅ 206 mod 911
≡ 103412 mod 911 ≡ 469 mod 911

Es gilt also: 842²²² ≡ 469 mod 911

Berechnung des größten gemeinsamen Teilers von 61 und 42

=>61	= 1⋅42 + 19
=>42	= 2⋅19 + 4
=>19	= 4⋅4 + 3
=>4	= 1⋅3 + 1
=>3	= 3⋅1 + 0

also gilt: ggt(61,42)=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= 4-1⋅3
3= 19-4⋅4	eingesetzt in die Zeile drüber:	1	= 1⋅4 -1⋅(19 -4⋅ 4) = 1⋅4 -1⋅19 +4⋅ 4) = -1⋅19 +5⋅ 4 (=1)
4= 42-2⋅19	eingesetzt in die Zeile drüber:	1	= -1⋅19 +5⋅(42 -2⋅ 19) = -1⋅19 +5⋅42 -10⋅ 19) = 5⋅42 -11⋅ 19 (=1)
19= 61-1⋅42	eingesetzt in die Zeile drüber:	1	= 5⋅42 -11⋅(61 -1⋅ 42) = 5⋅42 -11⋅61 +11⋅ 42) = -11⋅61 +16⋅ 42 (=1)

Es gilt also: ggt(61,42)=1 = -11⋅61 +16⋅42

oder wenn man -11⋅61 auf die linke Seite bringt:

1 +11⋅61 = +16⋅42

Es gilt also: 16⋅42 = 11⋅61 +1

Somit 16⋅42 = 1 mod 61

16 ist also das Inverse von 42 mod 61