Um längere Rechnungen zu vermeiden, rechnen wir:

(2405 + 117) mod 6 ≡ (2405 mod 6 + 117 mod 6) mod 6.

2405 mod 6 ≡ 5 mod 6 kann man relativ leicht bestimmen, weil ja 2405 = 2400+5 = 6 ⋅ 400 +5.

117 mod 6 ≡ 3 mod 6 kann man relativ leicht bestimmen, weil ja 117 = 120-3 = 6 ⋅ 20 -3 = 6 ⋅ 20 - 6 + 3.

Somit gilt:

(2405 + 117) mod 6 ≡ (5 + 3) mod 6 ≡ 8 mod 6 ≡ 2 mod 6.

Um längere Rechnungen zu vermeiden, rechnen wir:

(66 ⋅ 98) mod 4 ≡ (66 mod 4 ⋅ 98 mod 4) mod 4.

66 mod 4 ≡ 2 mod 4 kann man relativ leicht bestimmen, weil ja 66 = 64 + 2 = 16 ⋅ 4 + 2 ist.

98 mod 4 ≡ 2 mod 4 kann man relativ leicht bestimmen, weil ja 98 = 96 + 2 = 24 ⋅ 4 + 2 ist.

Somit gilt:

(66 ⋅ 98) mod 4 ≡ (2 ⋅ 2) mod 4 ≡ 4 mod 4 ≡ 0 mod 4.

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

2: 682²=682¹⁺¹=682¹⋅682¹ ≡ 682⋅682=465124 ≡ 336 mod 887

4: 682⁴=682²⁺²=682²⋅682² ≡ 336⋅336=112896 ≡ 247 mod 887

8: 682⁸=682⁴⁺⁴=682⁴⋅682⁴ ≡ 247⋅247=61009 ≡ 693 mod 887

16: 682¹⁶=682⁸⁺⁸=682⁸⋅682⁸ ≡ 693⋅693=480249 ≡ 382 mod 887

32: 682³²=682¹⁶⁺¹⁶=682¹⁶⋅682¹⁶ ≡ 382⋅382=145924 ≡ 456 mod 887

64: 682⁶⁴=682³²⁺³²=682³²⋅682³² ≡ 456⋅456=207936 ≡ 378 mod 887

128: 682¹²⁸=682⁶⁴⁺⁶⁴=682⁶⁴⋅682⁶⁴ ≡ 378⋅378=142884 ≡ 77 mod 887

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

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

178 = 128+32+16+2

421¹⁷⁸

= 421^128+32+16+2

= 421¹²⁸⋅421³²⋅421¹⁶⋅421²

≡ 396 ⋅ 36 ⋅ 485 ⋅ 481 mod 491
≡ 14256 ⋅ 485 ⋅ 481 mod 491 ≡ 17 ⋅ 485 ⋅ 481 mod 491
≡ 8245 ⋅ 481 mod 491 ≡ 389 ⋅ 481 mod 491
≡ 187109 mod 491 ≡ 38 mod 491

Es gilt also: 421¹⁷⁸ ≡ 38 mod 491

Berechnung des größten gemeinsamen Teilers von 59 und 27

=>59	= 2⋅27 + 5
=>27	= 5⋅5 + 2
=>5	= 2⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(59,27)=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= 5-2⋅2
2= 27-5⋅5	eingesetzt in die Zeile drüber:	1	= 1⋅5 -2⋅(27 -5⋅ 5) = 1⋅5 -2⋅27 +10⋅ 5) = -2⋅27 +11⋅ 5 (=1)
5= 59-2⋅27	eingesetzt in die Zeile drüber:	1	= -2⋅27 +11⋅(59 -2⋅ 27) = -2⋅27 +11⋅59 -22⋅ 27) = 11⋅59 -24⋅ 27 (=1)

Es gilt also: ggt(59,27)=1 = 11⋅59 -24⋅27

oder wenn man 11⋅59 auf die linke Seite bringt:

1 -11⋅59 = -24⋅27

-24⋅27 = -11⋅59 + 1 |+59⋅27

-24⋅27 + 59⋅27 = -11⋅59 + 59⋅27 + 1

(-24 + 59) ⋅ 27 = (-11 + 27) ⋅ 59 + 1

35⋅27 = 16⋅59 + 1

Es gilt also: 35⋅27 = 16⋅59 +1

Somit 35⋅27 = 1 mod 59

35 ist also das Inverse von 27 mod 59