Um längere Rechnungen zu vermeiden, rechnen wir:

(801 + 19998) mod 4 ≡ (801 mod 4 + 19998 mod 4) mod 4.

801 mod 4 ≡ 1 mod 4 kann man relativ leicht bestimmen, weil ja 801 = 800+1 = 4 ⋅ 200 +1.

19998 mod 4 ≡ 2 mod 4 kann man relativ leicht bestimmen, weil ja 19998 = 19000+998 = 4 ⋅ 4750 +998.

Somit gilt:

(801 + 19998) mod 4 ≡ (1 + 2) mod 4 ≡ 3 mod 4.

Um längere Rechnungen zu vermeiden, rechnen wir:

(58 ⋅ 81) mod 7 ≡ (58 mod 7 ⋅ 81 mod 7) mod 7.

58 mod 7 ≡ 2 mod 7 kann man relativ leicht bestimmen, weil ja 58 = 56 + 2 = 8 ⋅ 7 + 2 ist.

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

Somit gilt:

(58 ⋅ 81) mod 7 ≡ (2 ⋅ 4) mod 7 ≡ 8 mod 7 ≡ 1 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: 584¹=584

2: 584²=584¹⁺¹=584¹⋅584¹ ≡ 584⋅584=341056 ≡ 218 mod 883

4: 584⁴=584²⁺²=584²⋅584² ≡ 218⋅218=47524 ≡ 725 mod 883

8: 584⁸=584⁴⁺⁴=584⁴⋅584⁴ ≡ 725⋅725=525625 ≡ 240 mod 883

16: 584¹⁶=584⁸⁺⁸=584⁸⋅584⁸ ≡ 240⋅240=57600 ≡ 205 mod 883

32: 584³²=584¹⁶⁺¹⁶=584¹⁶⋅584¹⁶ ≡ 205⋅205=42025 ≡ 524 mod 883

64: 584⁶⁴=584³²⁺³²=584³²⋅584³² ≡ 524⋅524=274576 ≡ 846 mod 883

128: 584¹²⁸=584⁶⁴⁺⁶⁴=584⁶⁴⋅584⁶⁴ ≡ 846⋅846=715716 ≡ 486 mod 883

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

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

92 = 64+16+8+4

530⁹²

= 530^64+16+8+4

= 530⁶⁴⋅530¹⁶⋅530⁸⋅530⁴

≡ 110 ⋅ 102 ⋅ 596 ⋅ 293 mod 641
≡ 11220 ⋅ 596 ⋅ 293 mod 641 ≡ 323 ⋅ 596 ⋅ 293 mod 641
≡ 192508 ⋅ 293 mod 641 ≡ 208 ⋅ 293 mod 641
≡ 60944 mod 641 ≡ 49 mod 641

Es gilt also: 530⁹² ≡ 49 mod 641

Berechnung des größten gemeinsamen Teilers von 101 und 31

=>101	= 3⋅31 + 8
=>31	= 3⋅8 + 7
=>8	= 1⋅7 + 1
=>7	= 7⋅1 + 0

also gilt: ggt(101,31)=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= 8-1⋅7
7= 31-3⋅8	eingesetzt in die Zeile drüber:	1	= 1⋅8 -1⋅(31 -3⋅ 8) = 1⋅8 -1⋅31 +3⋅ 8) = -1⋅31 +4⋅ 8 (=1)
8= 101-3⋅31	eingesetzt in die Zeile drüber:	1	= -1⋅31 +4⋅(101 -3⋅ 31) = -1⋅31 +4⋅101 -12⋅ 31) = 4⋅101 -13⋅ 31 (=1)

Es gilt also: ggt(101,31)=1 = 4⋅101 -13⋅31

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

1 -4⋅101 = -13⋅31

-13⋅31 = -4⋅101 + 1 |+101⋅31

-13⋅31 + 101⋅31 = -4⋅101 + 101⋅31 + 1

(-13 + 101) ⋅ 31 = (-4 + 31) ⋅ 101 + 1

88⋅31 = 27⋅101 + 1

Es gilt also: 88⋅31 = 27⋅101 +1

Somit 88⋅31 = 1 mod 101

88 ist also das Inverse von 31 mod 101