Um längere Rechnungen zu vermeiden, rechnen wir:

(25000 - 14996) mod 5 ≡ (25000 mod 5 - 14996 mod 5) mod 5.

25000 mod 5 ≡ 0 mod 5 kann man relativ leicht bestimmen, weil ja 25000 = 25000+0 = 5 ⋅ 5000 +0.

14996 mod 5 ≡ 1 mod 5 kann man relativ leicht bestimmen, weil ja 14996 = 14000+996 = 5 ⋅ 2800 +996.

Somit gilt:

(25000 - 14996) mod 5 ≡ (0 - 1) mod 5 ≡ -1 mod 5 ≡ 4 mod 5.

Um längere Rechnungen zu vermeiden, rechnen wir:

(31 ⋅ 77) mod 9 ≡ (31 mod 9 ⋅ 77 mod 9) mod 9.

31 mod 9 ≡ 4 mod 9 kann man relativ leicht bestimmen, weil ja 31 = 27 + 4 = 3 ⋅ 9 + 4 ist.

77 mod 9 ≡ 5 mod 9 kann man relativ leicht bestimmen, weil ja 77 = 72 + 5 = 8 ⋅ 9 + 5 ist.

Somit gilt:

(31 ⋅ 77) mod 9 ≡ (4 ⋅ 5) mod 9 ≡ 20 mod 9 ≡ 2 mod 9.

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

2: 419²=419¹⁺¹=419¹⋅419¹ ≡ 419⋅419=175561 ≡ 144 mod 431

4: 419⁴=419²⁺²=419²⋅419² ≡ 144⋅144=20736 ≡ 48 mod 431

8: 419⁸=419⁴⁺⁴=419⁴⋅419⁴ ≡ 48⋅48=2304 ≡ 149 mod 431

16: 419¹⁶=419⁸⁺⁸=419⁸⋅419⁸ ≡ 149⋅149=22201 ≡ 220 mod 431

32: 419³²=419¹⁶⁺¹⁶=419¹⁶⋅419¹⁶ ≡ 220⋅220=48400 ≡ 128 mod 431

64: 419⁶⁴=419³²⁺³²=419³²⋅419³² ≡ 128⋅128=16384 ≡ 6 mod 431

128: 419¹²⁸=419⁶⁴⁺⁶⁴=419⁶⁴⋅419⁶⁴ ≡ 6⋅6=36 ≡ 36 mod 431

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

464¹⁷⁸

= 464^128+32+16+2

= 464¹²⁸⋅464³²⋅464¹⁶⋅464²

≡ 301 ⋅ 151 ⋅ 359 ⋅ 133 mod 613
≡ 45451 ⋅ 359 ⋅ 133 mod 613 ≡ 89 ⋅ 359 ⋅ 133 mod 613
≡ 31951 ⋅ 133 mod 613 ≡ 75 ⋅ 133 mod 613
≡ 9975 mod 613 ≡ 167 mod 613

Es gilt also: 464¹⁷⁸ ≡ 167 mod 613

Berechnung des größten gemeinsamen Teilers von 67 und 62

=>67	= 1⋅62 + 5
=>62	= 12⋅5 + 2
=>5	= 2⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(67,62)=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= 62-12⋅5	eingesetzt in die Zeile drüber:	1	= 1⋅5 -2⋅(62 -12⋅ 5) = 1⋅5 -2⋅62 +24⋅ 5) = -2⋅62 +25⋅ 5 (=1)
5= 67-1⋅62	eingesetzt in die Zeile drüber:	1	= -2⋅62 +25⋅(67 -1⋅ 62) = -2⋅62 +25⋅67 -25⋅ 62) = 25⋅67 -27⋅ 62 (=1)

Es gilt also: ggt(67,62)=1 = 25⋅67 -27⋅62

oder wenn man 25⋅67 auf die linke Seite bringt:

1 -25⋅67 = -27⋅62

-27⋅62 = -25⋅67 + 1 |+67⋅62

-27⋅62 + 67⋅62 = -25⋅67 + 67⋅62 + 1

(-27 + 67) ⋅ 62 = (-25 + 62) ⋅ 67 + 1

40⋅62 = 37⋅67 + 1

Es gilt also: 40⋅62 = 37⋅67 +1

Somit 40⋅62 = 1 mod 67

40 ist also das Inverse von 62 mod 67