Um längere Rechnungen zu vermeiden, rechnen wir:

(31999 - 792) mod 8 ≡ (31999 mod 8 - 792 mod 8) mod 8.

31999 mod 8 ≡ 7 mod 8 kann man relativ leicht bestimmen, weil ja 31999 = 31000+999 = 8 ⋅ 3875 +999.

792 mod 8 ≡ 0 mod 8 kann man relativ leicht bestimmen, weil ja 792 = 800-8 = 8 ⋅ 100 -8 = 8 ⋅ 100 - 8 + 0.

Somit gilt:

(31999 - 792) mod 8 ≡ (7 - 0) mod 8 ≡ 7 mod 8.

Um längere Rechnungen zu vermeiden, rechnen wir:

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

100 mod 7 ≡ 2 mod 7 kann man relativ leicht bestimmen, weil ja 100 = 98 + 2 = 14 ⋅ 7 + 2 ist.

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

Somit gilt:

(100 ⋅ 42) mod 7 ≡ (2 ⋅ 0) mod 7 ≡ 0 mod 7.

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

2: 272²=272¹⁺¹=272¹⋅272¹ ≡ 272⋅272=73984 ≡ 557 mod 727

4: 272⁴=272²⁺²=272²⋅272² ≡ 557⋅557=310249 ≡ 547 mod 727

8: 272⁸=272⁴⁺⁴=272⁴⋅272⁴ ≡ 547⋅547=299209 ≡ 412 mod 727

16: 272¹⁶=272⁸⁺⁸=272⁸⋅272⁸ ≡ 412⋅412=169744 ≡ 353 mod 727

32: 272³²=272¹⁶⁺¹⁶=272¹⁶⋅272¹⁶ ≡ 353⋅353=124609 ≡ 292 mod 727

64: 272⁶⁴=272³²⁺³²=272³²⋅272³² ≡ 292⋅292=85264 ≡ 205 mod 727

128: 272¹²⁸=272⁶⁴⁺⁶⁴=272⁶⁴⋅272⁶⁴ ≡ 205⋅205=42025 ≡ 586 mod 727

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

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

79 = 64+8+4+2+1

290⁷⁹

= 290^64+8+4+2+1

= 290⁶⁴⋅290⁸⋅290⁴⋅290²⋅290¹

≡ 94 ⋅ 267 ⋅ 240 ⋅ 407 ⋅ 290 mod 659
≡ 25098 ⋅ 240 ⋅ 407 ⋅ 290 mod 659 ≡ 56 ⋅ 240 ⋅ 407 ⋅ 290 mod 659
≡ 13440 ⋅ 407 ⋅ 290 mod 659 ≡ 260 ⋅ 407 ⋅ 290 mod 659
≡ 105820 ⋅ 290 mod 659 ≡ 380 ⋅ 290 mod 659
≡ 110200 mod 659 ≡ 147 mod 659

Es gilt also: 290⁷⁹ ≡ 147 mod 659

Berechnung des größten gemeinsamen Teilers von 89 und 71

=>89	= 1⋅71 + 18
=>71	= 3⋅18 + 17
=>18	= 1⋅17 + 1
=>17	= 17⋅1 + 0

also gilt: ggt(89,71)=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= 71-3⋅18	eingesetzt in die Zeile drüber:	1	= 1⋅18 -1⋅(71 -3⋅ 18) = 1⋅18 -1⋅71 +3⋅ 18) = -1⋅71 +4⋅ 18 (=1)
18= 89-1⋅71	eingesetzt in die Zeile drüber:	1	= -1⋅71 +4⋅(89 -1⋅ 71) = -1⋅71 +4⋅89 -4⋅ 71) = 4⋅89 -5⋅ 71 (=1)

Es gilt also: ggt(89,71)=1 = 4⋅89 -5⋅71

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

1 -4⋅89 = -5⋅71

-5⋅71 = -4⋅89 + 1 |+89⋅71

-5⋅71 + 89⋅71 = -4⋅89 + 89⋅71 + 1

(-5 + 89) ⋅ 71 = (-4 + 71) ⋅ 89 + 1

84⋅71 = 67⋅89 + 1

Es gilt also: 84⋅71 = 67⋅89 +1

Somit 84⋅71 = 1 mod 89

84 ist also das Inverse von 71 mod 89