Um längere Rechnungen zu vermeiden, rechnen wir:

(45002 + 2694) mod 9 ≡ (45002 mod 9 + 2694 mod 9) mod 9.

45002 mod 9 ≡ 2 mod 9 kann man relativ leicht bestimmen, weil ja 45002 = 45000+2 = 9 ⋅ 5000 +2.

2694 mod 9 ≡ 3 mod 9 kann man relativ leicht bestimmen, weil ja 2694 = 2700-6 = 9 ⋅ 300 -6 = 9 ⋅ 300 - 9 + 3.

Somit gilt:

(45002 + 2694) mod 9 ≡ (2 + 3) mod 9 ≡ 5 mod 9.

Um längere Rechnungen zu vermeiden, rechnen wir:

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

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

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

Somit gilt:

(78 ⋅ 82) mod 11 ≡ (1 ⋅ 5) mod 11 ≡ 5 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: 320¹=320

2: 320²=320¹⁺¹=320¹⋅320¹ ≡ 320⋅320=102400 ≡ 77 mod 463

4: 320⁴=320²⁺²=320²⋅320² ≡ 77⋅77=5929 ≡ 373 mod 463

8: 320⁸=320⁴⁺⁴=320⁴⋅320⁴ ≡ 373⋅373=139129 ≡ 229 mod 463

16: 320¹⁶=320⁸⁺⁸=320⁸⋅320⁸ ≡ 229⋅229=52441 ≡ 122 mod 463

32: 320³²=320¹⁶⁺¹⁶=320¹⁶⋅320¹⁶ ≡ 122⋅122=14884 ≡ 68 mod 463

64: 320⁶⁴=320³²⁺³²=320³²⋅320³² ≡ 68⋅68=4624 ≡ 457 mod 463

128: 320¹²⁸=320⁶⁴⁺⁶⁴=320⁶⁴⋅320⁶⁴ ≡ 457⋅457=208849 ≡ 36 mod 463

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

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

242 = 128+64+32+16+2

264²⁴²

= 264^{128+64+32+16+2}

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

≡ 60 ⋅ 158 ⋅ 262 ⋅ 230 ⋅ 78 mod 283
≡ 9480 ⋅ 262 ⋅ 230 ⋅ 78 mod 283 ≡ 141 ⋅ 262 ⋅ 230 ⋅ 78 mod 283
≡ 36942 ⋅ 230 ⋅ 78 mod 283 ≡ 152 ⋅ 230 ⋅ 78 mod 283
≡ 34960 ⋅ 78 mod 283 ≡ 151 ⋅ 78 mod 283
≡ 11778 mod 283 ≡ 175 mod 283

Es gilt also: 264²⁴² ≡ 175 mod 283

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

=>71	= 1⋅55 + 16
=>55	= 3⋅16 + 7
=>16	= 2⋅7 + 2
=>7	= 3⋅2 + 1
=>2	= 2⋅1 + 0

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

Es gilt also: ggt(71,55)=1 = -24⋅71 +31⋅55

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

1 +24⋅71 = +31⋅55

Es gilt also: 31⋅55 = 24⋅71 +1

Somit 31⋅55 = 1 mod 71

31 ist also das Inverse von 55 mod 71