Um längere Rechnungen zu vermeiden, rechnen wir:

(12000 - 1497) mod 3 ≡ (12000 mod 3 - 1497 mod 3) mod 3.

12000 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 12000 = 12000+0 = 3 ⋅ 4000 +0.

1497 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 1497 = 1500-3 = 3 ⋅ 500 -3 = 3 ⋅ 500 - 3 + 0.

Somit gilt:

(12000 - 1497) mod 3 ≡ (0 - 0) mod 3 ≡ 0 mod 3.

Um längere Rechnungen zu vermeiden, rechnen wir:

(78 ⋅ 98) mod 3 ≡ (78 mod 3 ⋅ 98 mod 3) mod 3.

78 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 78 = 78 + 0 = 26 ⋅ 3 + 0 ist.

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

Somit gilt:

(78 ⋅ 98) mod 3 ≡ (0 ⋅ 2) mod 3 ≡ 0 mod 3.

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

2: 503²=503¹⁺¹=503¹⋅503¹ ≡ 503⋅503=253009 ≡ 360 mod 797

4: 503⁴=503²⁺²=503²⋅503² ≡ 360⋅360=129600 ≡ 486 mod 797

8: 503⁸=503⁴⁺⁴=503⁴⋅503⁴ ≡ 486⋅486=236196 ≡ 284 mod 797

16: 503¹⁶=503⁸⁺⁸=503⁸⋅503⁸ ≡ 284⋅284=80656 ≡ 159 mod 797

32: 503³²=503¹⁶⁺¹⁶=503¹⁶⋅503¹⁶ ≡ 159⋅159=25281 ≡ 574 mod 797

64: 503⁶⁴=503³²⁺³²=503³²⋅503³² ≡ 574⋅574=329476 ≡ 315 mod 797

128: 503¹²⁸=503⁶⁴⁺⁶⁴=503⁶⁴⋅503⁶⁴ ≡ 315⋅315=99225 ≡ 397 mod 797

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

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

151 = 128+16+4+2+1

306¹⁵¹

= 306^128+16+4+2+1

= 306¹²⁸⋅306¹⁶⋅306⁴⋅306²⋅306¹

≡ 615 ⋅ 186 ⋅ 127 ⋅ 65 ⋅ 306 mod 683
≡ 114390 ⋅ 127 ⋅ 65 ⋅ 306 mod 683 ≡ 329 ⋅ 127 ⋅ 65 ⋅ 306 mod 683
≡ 41783 ⋅ 65 ⋅ 306 mod 683 ≡ 120 ⋅ 65 ⋅ 306 mod 683
≡ 7800 ⋅ 306 mod 683 ≡ 287 ⋅ 306 mod 683
≡ 87822 mod 683 ≡ 398 mod 683

Es gilt also: 306¹⁵¹ ≡ 398 mod 683

Berechnung des größten gemeinsamen Teilers von 89 und 35

=>89	= 2⋅35 + 19
=>35	= 1⋅19 + 16
=>19	= 1⋅16 + 3
=>16	= 5⋅3 + 1
=>3	= 3⋅1 + 0

also gilt: ggt(89,35)=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= 16-5⋅3
3= 19-1⋅16	eingesetzt in die Zeile drüber:	1	= 1⋅16 -5⋅(19 -1⋅ 16) = 1⋅16 -5⋅19 +5⋅ 16) = -5⋅19 +6⋅ 16 (=1)
16= 35-1⋅19	eingesetzt in die Zeile drüber:	1	= -5⋅19 +6⋅(35 -1⋅ 19) = -5⋅19 +6⋅35 -6⋅ 19) = 6⋅35 -11⋅ 19 (=1)
19= 89-2⋅35	eingesetzt in die Zeile drüber:	1	= 6⋅35 -11⋅(89 -2⋅ 35) = 6⋅35 -11⋅89 +22⋅ 35) = -11⋅89 +28⋅ 35 (=1)

Es gilt also: ggt(89,35)=1 = -11⋅89 +28⋅35

oder wenn man -11⋅89 auf die linke Seite bringt:

1 +11⋅89 = +28⋅35

Es gilt also: 28⋅35 = 11⋅89 +1

Somit 28⋅35 = 1 mod 89

28 ist also das Inverse von 35 mod 89