Um längere Rechnungen zu vermeiden, rechnen wir:

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

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

1498 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 1498 = 1500-2 = 3 ⋅ 500 -2 = 3 ⋅ 500 - 3 + 1.

Somit gilt:

(12000 - 1498) mod 3 ≡ (0 - 1) mod 3 ≡ -1 mod 3 ≡ 2 mod 3.

Um längere Rechnungen zu vermeiden, rechnen wir:

(64 ⋅ 96) mod 9 ≡ (64 mod 9 ⋅ 96 mod 9) mod 9.

64 mod 9 ≡ 1 mod 9 kann man relativ leicht bestimmen, weil ja 64 = 63 + 1 = 7 ⋅ 9 + 1 ist.

96 mod 9 ≡ 6 mod 9 kann man relativ leicht bestimmen, weil ja 96 = 90 + 6 = 10 ⋅ 9 + 6 ist.

Somit gilt:

(64 ⋅ 96) mod 9 ≡ (1 ⋅ 6) mod 9 ≡ 6 mod 9.

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

2: 252²=252¹⁺¹=252¹⋅252¹ ≡ 252⋅252=63504 ≡ 155 mod 443

4: 252⁴=252²⁺²=252²⋅252² ≡ 155⋅155=24025 ≡ 103 mod 443

8: 252⁸=252⁴⁺⁴=252⁴⋅252⁴ ≡ 103⋅103=10609 ≡ 420 mod 443

16: 252¹⁶=252⁸⁺⁸=252⁸⋅252⁸ ≡ 420⋅420=176400 ≡ 86 mod 443

32: 252³²=252¹⁶⁺¹⁶=252¹⁶⋅252¹⁶ ≡ 86⋅86=7396 ≡ 308 mod 443

64: 252⁶⁴=252³²⁺³²=252³²⋅252³² ≡ 308⋅308=94864 ≡ 62 mod 443

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

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

226 = 128+64+32+2

548²²⁶

= 548^128+64+32+2

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

≡ 246 ⋅ 426 ⋅ 446 ⋅ 843 mod 863
≡ 104796 ⋅ 446 ⋅ 843 mod 863 ≡ 373 ⋅ 446 ⋅ 843 mod 863
≡ 166358 ⋅ 843 mod 863 ≡ 662 ⋅ 843 mod 863
≡ 558066 mod 863 ≡ 568 mod 863

Es gilt also: 548²²⁶ ≡ 568 mod 863

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

=>97	= 1⋅58 + 39
=>58	= 1⋅39 + 19
=>39	= 2⋅19 + 1
=>19	= 19⋅1 + 0

also gilt: ggt(97,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= 39-2⋅19
19= 58-1⋅39	eingesetzt in die Zeile drüber:	1	= 1⋅39 -2⋅(58 -1⋅ 39) = 1⋅39 -2⋅58 +2⋅ 39) = -2⋅58 +3⋅ 39 (=1)
39= 97-1⋅58	eingesetzt in die Zeile drüber:	1	= -2⋅58 +3⋅(97 -1⋅ 58) = -2⋅58 +3⋅97 -3⋅ 58) = 3⋅97 -5⋅ 58 (=1)

Es gilt also: ggt(97,58)=1 = 3⋅97 -5⋅58

oder wenn man 3⋅97 auf die linke Seite bringt:

1 -3⋅97 = -5⋅58

-5⋅58 = -3⋅97 + 1 |+97⋅58

-5⋅58 + 97⋅58 = -3⋅97 + 97⋅58 + 1

(-5 + 97) ⋅ 58 = (-3 + 58) ⋅ 97 + 1

92⋅58 = 55⋅97 + 1

Es gilt also: 92⋅58 = 55⋅97 +1

Somit 92⋅58 = 1 mod 97

92 ist also das Inverse von 58 mod 97