Um längere Rechnungen zu vermeiden, rechnen wir:

(2100 - 27993) mod 7 ≡ (2100 mod 7 - 27993 mod 7) mod 7.

2100 mod 7 ≡ 0 mod 7 kann man relativ leicht bestimmen, weil ja 2100 = 2100+0 = 7 ⋅ 300 +0.

27993 mod 7 ≡ 0 mod 7 kann man relativ leicht bestimmen, weil ja 27993 = 28000-7 = 7 ⋅ 4000 -7 = 7 ⋅ 4000 - 7 + 0.

Somit gilt:

(2100 - 27993) mod 7 ≡ (0 - 0) mod 7 ≡ 0 mod 7.

Um längere Rechnungen zu vermeiden, rechnen wir:

(88 ⋅ 95) mod 8 ≡ (88 mod 8 ⋅ 95 mod 8) mod 8.

88 mod 8 ≡ 0 mod 8 kann man relativ leicht bestimmen, weil ja 88 = 88 + 0 = 11 ⋅ 8 + 0 ist.

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

Somit gilt:

(88 ⋅ 95) mod 8 ≡ (0 ⋅ 7) mod 8 ≡ 0 mod 8.

Die 64 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: 324¹=324

2: 324²=324¹⁺¹=324¹⋅324¹ ≡ 324⋅324=104976 ≡ 719 mod 761

4: 324⁴=324²⁺²=324²⋅324² ≡ 719⋅719=516961 ≡ 242 mod 761

8: 324⁸=324⁴⁺⁴=324⁴⋅324⁴ ≡ 242⋅242=58564 ≡ 728 mod 761

16: 324¹⁶=324⁸⁺⁸=324⁸⋅324⁸ ≡ 728⋅728=529984 ≡ 328 mod 761

32: 324³²=324¹⁶⁺¹⁶=324¹⁶⋅324¹⁶ ≡ 328⋅328=107584 ≡ 283 mod 761

64: 324⁶⁴=324³²⁺³²=324³²⋅324³² ≡ 283⋅283=80089 ≡ 184 mod 761

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

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

166 = 128+32+4+2

371¹⁶⁶

= 371^128+32+4+2

= 371¹²⁸⋅371³²⋅371⁴⋅371²

≡ 655 ⋅ 223 ⋅ 760 ⋅ 703 mod 787
≡ 146065 ⋅ 760 ⋅ 703 mod 787 ≡ 470 ⋅ 760 ⋅ 703 mod 787
≡ 357200 ⋅ 703 mod 787 ≡ 689 ⋅ 703 mod 787
≡ 484367 mod 787 ≡ 362 mod 787

Es gilt also: 371¹⁶⁶ ≡ 362 mod 787

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

=>67	= 1⋅42 + 25
=>42	= 1⋅25 + 17
=>25	= 1⋅17 + 8
=>17	= 2⋅8 + 1
=>8	= 8⋅1 + 0

also gilt: ggt(67,42)=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= 17-2⋅8
8= 25-1⋅17	eingesetzt in die Zeile drüber:	1	= 1⋅17 -2⋅(25 -1⋅ 17) = 1⋅17 -2⋅25 +2⋅ 17) = -2⋅25 +3⋅ 17 (=1)
17= 42-1⋅25	eingesetzt in die Zeile drüber:	1	= -2⋅25 +3⋅(42 -1⋅ 25) = -2⋅25 +3⋅42 -3⋅ 25) = 3⋅42 -5⋅ 25 (=1)
25= 67-1⋅42	eingesetzt in die Zeile drüber:	1	= 3⋅42 -5⋅(67 -1⋅ 42) = 3⋅42 -5⋅67 +5⋅ 42) = -5⋅67 +8⋅ 42 (=1)

Es gilt also: ggt(67,42)=1 = -5⋅67 +8⋅42

oder wenn man -5⋅67 auf die linke Seite bringt:

1 +5⋅67 = +8⋅42

Es gilt also: 8⋅42 = 5⋅67 +1

Somit 8⋅42 = 1 mod 67

8 ist also das Inverse von 42 mod 67