Um längere Rechnungen zu vermeiden, rechnen wir:

(14005 - 27998) mod 7 ≡ (14005 mod 7 - 27998 mod 7) mod 7.

14005 mod 7 ≡ 5 mod 7 kann man relativ leicht bestimmen, weil ja 14005 = 14000+5 = 7 ⋅ 2000 +5.

27998 mod 7 ≡ 5 mod 7 kann man relativ leicht bestimmen, weil ja 27998 = 28000-2 = 7 ⋅ 4000 -2 = 7 ⋅ 4000 - 7 + 5.

Somit gilt:

(14005 - 27998) mod 7 ≡ (5 - 5) mod 7 ≡ 0 mod 7.

Um längere Rechnungen zu vermeiden, rechnen wir:

(35 ⋅ 20) mod 10 ≡ (35 mod 10 ⋅ 20 mod 10) mod 10.

35 mod 10 ≡ 5 mod 10 kann man relativ leicht bestimmen, weil ja 35 = 30 + 5 = 3 ⋅ 10 + 5 ist.

20 mod 10 ≡ 0 mod 10 kann man relativ leicht bestimmen, weil ja 20 = 20 + 0 = 2 ⋅ 10 + 0 ist.

Somit gilt:

(35 ⋅ 20) mod 10 ≡ (5 ⋅ 0) mod 10 ≡ 0 mod 10.

Die 32 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: 510¹=510

2: 510²=510¹⁺¹=510¹⋅510¹ ≡ 510⋅510=260100 ≡ 390 mod 787

4: 510⁴=510²⁺²=510²⋅510² ≡ 390⋅390=152100 ≡ 209 mod 787

8: 510⁸=510⁴⁺⁴=510⁴⋅510⁴ ≡ 209⋅209=43681 ≡ 396 mod 787

16: 510¹⁶=510⁸⁺⁸=510⁸⋅510⁸ ≡ 396⋅396=156816 ≡ 203 mod 787

32: 510³²=510¹⁶⁺¹⁶=510¹⁶⋅510¹⁶ ≡ 203⋅203=41209 ≡ 285 mod 787

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

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

237 = 128+64+32+8+4+1

455²³⁷

= 455^{128+64+32+8+4+1}

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

≡ 216 ⋅ 125 ⋅ 526 ⋅ 287 ⋅ 551 ⋅ 455 mod 811
≡ 27000 ⋅ 526 ⋅ 287 ⋅ 551 ⋅ 455 mod 811 ≡ 237 ⋅ 526 ⋅ 287 ⋅ 551 ⋅ 455 mod 811
≡ 124662 ⋅ 287 ⋅ 551 ⋅ 455 mod 811 ≡ 579 ⋅ 287 ⋅ 551 ⋅ 455 mod 811
≡ 166173 ⋅ 551 ⋅ 455 mod 811 ≡ 729 ⋅ 551 ⋅ 455 mod 811
≡ 401679 ⋅ 455 mod 811 ≡ 234 ⋅ 455 mod 811
≡ 106470 mod 811 ≡ 229 mod 811

Es gilt also: 455²³⁷ ≡ 229 mod 811

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

=>67	= 1⋅58 + 9
=>58	= 6⋅9 + 4
=>9	= 2⋅4 + 1
=>4	= 4⋅1 + 0

also gilt: ggt(67,58)=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= 58-6⋅9	eingesetzt in die Zeile drüber:	1	= 1⋅9 -2⋅(58 -6⋅ 9) = 1⋅9 -2⋅58 +12⋅ 9) = -2⋅58 +13⋅ 9 (=1)
9= 67-1⋅58	eingesetzt in die Zeile drüber:	1	= -2⋅58 +13⋅(67 -1⋅ 58) = -2⋅58 +13⋅67 -13⋅ 58) = 13⋅67 -15⋅ 58 (=1)

Es gilt also: ggt(67,58)=1 = 13⋅67 -15⋅58

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

1 -13⋅67 = -15⋅58

-15⋅58 = -13⋅67 + 1 |+67⋅58

-15⋅58 + 67⋅58 = -13⋅67 + 67⋅58 + 1

(-15 + 67) ⋅ 58 = (-13 + 58) ⋅ 67 + 1

52⋅58 = 45⋅67 + 1

Es gilt also: 52⋅58 = 45⋅67 +1

Somit 52⋅58 = 1 mod 67

52 ist also das Inverse von 58 mod 67