Um längere Rechnungen zu vermeiden, rechnen wir:

(71 - 28001) mod 7 ≡ (71 mod 7 - 28001 mod 7) mod 7.

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

28001 mod 7 ≡ 1 mod 7 kann man relativ leicht bestimmen, weil ja 28001 = 28000+1 = 7 ⋅ 4000 +1.

Somit gilt:

(71 - 28001) mod 7 ≡ (1 - 1) mod 7 ≡ 0 mod 7.

Um längere Rechnungen zu vermeiden, rechnen wir:

(51 ⋅ 85) mod 3 ≡ (51 mod 3 ⋅ 85 mod 3) mod 3.

51 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 51 = 51 + 0 = 17 ⋅ 3 + 0 ist.

85 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 85 = 84 + 1 = 28 ⋅ 3 + 1 ist.

Somit gilt:

(51 ⋅ 85) mod 3 ≡ (0 ⋅ 1) mod 3 ≡ 0 mod 3.

Die 16 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: 176¹=176

2: 176²=176¹⁺¹=176¹⋅176¹ ≡ 176⋅176=30976 ≡ 139 mod 541

4: 176⁴=176²⁺²=176²⋅176² ≡ 139⋅139=19321 ≡ 386 mod 541

8: 176⁸=176⁴⁺⁴=176⁴⋅176⁴ ≡ 386⋅386=148996 ≡ 221 mod 541

16: 176¹⁶=176⁸⁺⁸=176⁸⋅176⁸ ≡ 221⋅221=48841 ≡ 151 mod 541

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

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

243 = 128+64+32+16+2+1

153²⁴³

= 153^{128+64+32+16+2+1}

= 153¹²⁸⋅153⁶⁴⋅153³²⋅153¹⁶⋅153²⋅153¹

≡ 104 ⋅ 34 ⋅ 49 ⋅ 256 ⋅ 2 ⋅ 153 mod 263
≡ 3536 ⋅ 49 ⋅ 256 ⋅ 2 ⋅ 153 mod 263 ≡ 117 ⋅ 49 ⋅ 256 ⋅ 2 ⋅ 153 mod 263
≡ 5733 ⋅ 256 ⋅ 2 ⋅ 153 mod 263 ≡ 210 ⋅ 256 ⋅ 2 ⋅ 153 mod 263
≡ 53760 ⋅ 2 ⋅ 153 mod 263 ≡ 108 ⋅ 2 ⋅ 153 mod 263
≡ 216 ⋅ 153 mod 263
≡ 33048 mod 263 ≡ 173 mod 263

Es gilt also: 153²⁴³ ≡ 173 mod 263

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

=>89	= 1⋅79 + 10
=>79	= 7⋅10 + 9
=>10	= 1⋅9 + 1
=>9	= 9⋅1 + 0

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

Es gilt also: ggt(89,79)=1 = 8⋅89 -9⋅79

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

1 -8⋅89 = -9⋅79

-9⋅79 = -8⋅89 + 1 |+89⋅79

-9⋅79 + 89⋅79 = -8⋅89 + 89⋅79 + 1

(-9 + 89) ⋅ 79 = (-8 + 79) ⋅ 89 + 1

80⋅79 = 71⋅89 + 1

Es gilt also: 80⋅79 = 71⋅89 +1

Somit 80⋅79 = 1 mod 89

80 ist also das Inverse von 79 mod 89