Um längere Rechnungen zu vermeiden, rechnen wir:

(27993 - 3497) mod 7 ≡ (27993 mod 7 - 3497 mod 7) mod 7.

27993 mod 7 ≡ 0 mod 7 kann man relativ leicht bestimmen, weil ja 27993 = 28000-7 = 7 ⋅ 4000 -7 = 7 ⋅ 4000 - 7 + 0.

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

Somit gilt:

(27993 - 3497) mod 7 ≡ (0 - 4) mod 7 ≡ -4 mod 7 ≡ 3 mod 7.

Um längere Rechnungen zu vermeiden, rechnen wir:

(84 ⋅ 65) mod 11 ≡ (84 mod 11 ⋅ 65 mod 11) mod 11.

84 mod 11 ≡ 7 mod 11 kann man relativ leicht bestimmen, weil ja 84 = 77 + 7 = 7 ⋅ 11 + 7 ist.

65 mod 11 ≡ 10 mod 11 kann man relativ leicht bestimmen, weil ja 65 = 55 + 10 = 5 ⋅ 11 + 10 ist.

Somit gilt:

(84 ⋅ 65) mod 11 ≡ (7 ⋅ 10) mod 11 ≡ 70 mod 11 ≡ 4 mod 11.

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

2: 226²=226¹⁺¹=226¹⋅226¹ ≡ 226⋅226=51076 ≡ 610 mod 647

4: 226⁴=226²⁺²=226²⋅226² ≡ 610⋅610=372100 ≡ 75 mod 647

8: 226⁸=226⁴⁺⁴=226⁴⋅226⁴ ≡ 75⋅75=5625 ≡ 449 mod 647

16: 226¹⁶=226⁸⁺⁸=226⁸⋅226⁸ ≡ 449⋅449=201601 ≡ 384 mod 647

32: 226³²=226¹⁶⁺¹⁶=226¹⁶⋅226¹⁶ ≡ 384⋅384=147456 ≡ 587 mod 647

64: 226⁶⁴=226³²⁺³²=226³²⋅226³² ≡ 587⋅587=344569 ≡ 365 mod 647

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

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

201 = 128+64+8+1

132²⁰¹

= 132^128+64+8+1

= 132¹²⁸⋅132⁶⁴⋅132⁸⋅132¹

≡ 127 ⋅ 48 ⋅ 53 ⋅ 132 mod 311
≡ 6096 ⋅ 53 ⋅ 132 mod 311 ≡ 187 ⋅ 53 ⋅ 132 mod 311
≡ 9911 ⋅ 132 mod 311 ≡ 270 ⋅ 132 mod 311
≡ 35640 mod 311 ≡ 186 mod 311

Es gilt also: 132²⁰¹ ≡ 186 mod 311

Berechnung des größten gemeinsamen Teilers von 53 und 35

=>53	= 1⋅35 + 18
=>35	= 1⋅18 + 17
=>18	= 1⋅17 + 1
=>17	= 17⋅1 + 0

also gilt: ggt(53,35)=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= 18-1⋅17
17= 35-1⋅18	eingesetzt in die Zeile drüber:	1	= 1⋅18 -1⋅(35 -1⋅ 18) = 1⋅18 -1⋅35 +1⋅ 18) = -1⋅35 +2⋅ 18 (=1)
18= 53-1⋅35	eingesetzt in die Zeile drüber:	1	= -1⋅35 +2⋅(53 -1⋅ 35) = -1⋅35 +2⋅53 -2⋅ 35) = 2⋅53 -3⋅ 35 (=1)

Es gilt also: ggt(53,35)=1 = 2⋅53 -3⋅35

oder wenn man 2⋅53 auf die linke Seite bringt:

1 -2⋅53 = -3⋅35

-3⋅35 = -2⋅53 + 1 |+53⋅35

-3⋅35 + 53⋅35 = -2⋅53 + 53⋅35 + 1

(-3 + 53) ⋅ 35 = (-2 + 35) ⋅ 53 + 1

50⋅35 = 33⋅53 + 1

Es gilt also: 50⋅35 = 33⋅53 +1

Somit 50⋅35 = 1 mod 53

50 ist also das Inverse von 35 mod 53