Um längere Rechnungen zu vermeiden, rechnen wir:

(93 - 298) mod 3 ≡ (93 mod 3 - 298 mod 3) mod 3.

93 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 93 = 90+3 = 3 ⋅ 30 +3.

298 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 298 = 300-2 = 3 ⋅ 100 -2 = 3 ⋅ 100 - 3 + 1.

Somit gilt:

(93 - 298) mod 3 ≡ (0 - 1) mod 3 ≡ -1 mod 3 ≡ 2 mod 3.

Um längere Rechnungen zu vermeiden, rechnen wir:

(35 ⋅ 98) mod 5 ≡ (35 mod 5 ⋅ 98 mod 5) mod 5.

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

98 mod 5 ≡ 3 mod 5 kann man relativ leicht bestimmen, weil ja 98 = 95 + 3 = 19 ⋅ 5 + 3 ist.

Somit gilt:

(35 ⋅ 98) mod 5 ≡ (0 ⋅ 3) mod 5 ≡ 0 mod 5.

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

2: 192²=192¹⁺¹=192¹⋅192¹ ≡ 192⋅192=36864 ≡ 373 mod 401

4: 192⁴=192²⁺²=192²⋅192² ≡ 373⋅373=139129 ≡ 383 mod 401

8: 192⁸=192⁴⁺⁴=192⁴⋅192⁴ ≡ 383⋅383=146689 ≡ 324 mod 401

16: 192¹⁶=192⁸⁺⁸=192⁸⋅192⁸ ≡ 324⋅324=104976 ≡ 315 mod 401

32: 192³²=192¹⁶⁺¹⁶=192¹⁶⋅192¹⁶ ≡ 315⋅315=99225 ≡ 178 mod 401

64: 192⁶⁴=192³²⁺³²=192³²⋅192³² ≡ 178⋅178=31684 ≡ 5 mod 401

128: 192¹²⁸=192⁶⁴⁺⁶⁴=192⁶⁴⋅192⁶⁴ ≡ 5⋅5=25 ≡ 25 mod 401

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

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

179 = 128+32+16+2+1

667¹⁷⁹

= 667^{128+32+16+2+1}

= 667¹²⁸⋅667³²⋅667¹⁶⋅667²⋅667¹

≡ 707 ⋅ 542 ⋅ 593 ⋅ 691 ⋅ 667 mod 733
≡ 383194 ⋅ 593 ⋅ 691 ⋅ 667 mod 733 ≡ 568 ⋅ 593 ⋅ 691 ⋅ 667 mod 733
≡ 336824 ⋅ 691 ⋅ 667 mod 733 ≡ 377 ⋅ 691 ⋅ 667 mod 733
≡ 260507 ⋅ 667 mod 733 ≡ 292 ⋅ 667 mod 733
≡ 194764 mod 733 ≡ 519 mod 733

Es gilt also: 667¹⁷⁹ ≡ 519 mod 733

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

=>79	= 2⋅35 + 9
=>35	= 3⋅9 + 8
=>9	= 1⋅8 + 1
=>8	= 8⋅1 + 0

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

Es gilt also: ggt(79,35)=1 = 4⋅79 -9⋅35

oder wenn man 4⋅79 auf die linke Seite bringt:

1 -4⋅79 = -9⋅35

-9⋅35 = -4⋅79 + 1 |+79⋅35

-9⋅35 + 79⋅35 = -4⋅79 + 79⋅35 + 1

(-9 + 79) ⋅ 35 = (-4 + 35) ⋅ 79 + 1

70⋅35 = 31⋅79 + 1

Es gilt also: 70⋅35 = 31⋅79 +1

Somit 70⋅35 = 1 mod 79

70 ist also das Inverse von 35 mod 79