Um längere Rechnungen zu vermeiden, rechnen wir:

(150 + 1498) mod 3 ≡ (150 mod 3 + 1498 mod 3) mod 3.

150 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 150 = 150+0 = 3 ⋅ 50 +0.

1498 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 1498 = 1500-2 = 3 ⋅ 500 -2 = 3 ⋅ 500 - 3 + 1.

Somit gilt:

(150 + 1498) mod 3 ≡ (0 + 1) mod 3 ≡ 1 mod 3.

Um längere Rechnungen zu vermeiden, rechnen wir:

(78 ⋅ 85) mod 11 ≡ (78 mod 11 ⋅ 85 mod 11) mod 11.

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

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

Somit gilt:

(78 ⋅ 85) mod 11 ≡ (1 ⋅ 8) mod 11 ≡ 8 mod 11.

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

2: 486²=486¹⁺¹=486¹⋅486¹ ≡ 486⋅486=236196 ≡ 768 mod 853

4: 486⁴=486²⁺²=486²⋅486² ≡ 768⋅768=589824 ≡ 401 mod 853

8: 486⁸=486⁴⁺⁴=486⁴⋅486⁴ ≡ 401⋅401=160801 ≡ 437 mod 853

16: 486¹⁶=486⁸⁺⁸=486⁸⋅486⁸ ≡ 437⋅437=190969 ≡ 750 mod 853

32: 486³²=486¹⁶⁺¹⁶=486¹⁶⋅486¹⁶ ≡ 750⋅750=562500 ≡ 373 mod 853

64: 486⁶⁴=486³²⁺³²=486³²⋅486³² ≡ 373⋅373=139129 ≡ 90 mod 853

128: 486¹²⁸=486⁶⁴⁺⁶⁴=486⁶⁴⋅486⁶⁴ ≡ 90⋅90=8100 ≡ 423 mod 853

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

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

245 = 128+64+32+16+4+1

822²⁴⁵

= 822^{128+64+32+16+4+1}

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

≡ 175 ⋅ 784 ⋅ 28 ⋅ 919 ⋅ 654 ⋅ 822 mod 1009
≡ 137200 ⋅ 28 ⋅ 919 ⋅ 654 ⋅ 822 mod 1009 ≡ 985 ⋅ 28 ⋅ 919 ⋅ 654 ⋅ 822 mod 1009
≡ 27580 ⋅ 919 ⋅ 654 ⋅ 822 mod 1009 ≡ 337 ⋅ 919 ⋅ 654 ⋅ 822 mod 1009
≡ 309703 ⋅ 654 ⋅ 822 mod 1009 ≡ 949 ⋅ 654 ⋅ 822 mod 1009
≡ 620646 ⋅ 822 mod 1009 ≡ 111 ⋅ 822 mod 1009
≡ 91242 mod 1009 ≡ 432 mod 1009

Es gilt also: 822²⁴⁵ ≡ 432 mod 1009

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

=>71	= 1⋅40 + 31
=>40	= 1⋅31 + 9
=>31	= 3⋅9 + 4
=>9	= 2⋅4 + 1
=>4	= 4⋅1 + 0

also gilt: ggt(71,40)=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-2⋅4
4= 31-3⋅9	eingesetzt in die Zeile drüber:	1	= 1⋅9 -2⋅(31 -3⋅ 9) = 1⋅9 -2⋅31 +6⋅ 9) = -2⋅31 +7⋅ 9 (=1)
9= 40-1⋅31	eingesetzt in die Zeile drüber:	1	= -2⋅31 +7⋅(40 -1⋅ 31) = -2⋅31 +7⋅40 -7⋅ 31) = 7⋅40 -9⋅ 31 (=1)
31= 71-1⋅40	eingesetzt in die Zeile drüber:	1	= 7⋅40 -9⋅(71 -1⋅ 40) = 7⋅40 -9⋅71 +9⋅ 40) = -9⋅71 +16⋅ 40 (=1)

Es gilt also: ggt(71,40)=1 = -9⋅71 +16⋅40

oder wenn man -9⋅71 auf die linke Seite bringt:

1 +9⋅71 = +16⋅40

Es gilt also: 16⋅40 = 9⋅71 +1

Somit 16⋅40 = 1 mod 71

16 ist also das Inverse von 40 mod 71