Um längere Rechnungen zu vermeiden, rechnen wir:

(28000 - 1394) mod 7 ≡ (28000 mod 7 - 1394 mod 7) mod 7.

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

1394 mod 7 ≡ 1 mod 7 kann man relativ leicht bestimmen, weil ja 1394 = 1400-6 = 7 ⋅ 200 -6 = 7 ⋅ 200 - 7 + 1.

Somit gilt:

(28000 - 1394) mod 7 ≡ (0 - 1) mod 7 ≡ -1 mod 7 ≡ 6 mod 7.

Um längere Rechnungen zu vermeiden, rechnen wir:

(33 ⋅ 52) mod 3 ≡ (33 mod 3 ⋅ 52 mod 3) mod 3.

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

52 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 52 = 51 + 1 = 17 ⋅ 3 + 1 ist.

Somit gilt:

(33 ⋅ 52) mod 3 ≡ (0 ⋅ 1) 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: 590¹=590

2: 590²=590¹⁺¹=590¹⋅590¹ ≡ 590⋅590=348100 ≡ 159 mod 673

4: 590⁴=590²⁺²=590²⋅590² ≡ 159⋅159=25281 ≡ 380 mod 673

8: 590⁸=590⁴⁺⁴=590⁴⋅590⁴ ≡ 380⋅380=144400 ≡ 378 mod 673

16: 590¹⁶=590⁸⁺⁸=590⁸⋅590⁸ ≡ 378⋅378=142884 ≡ 208 mod 673

32: 590³²=590¹⁶⁺¹⁶=590¹⁶⋅590¹⁶ ≡ 208⋅208=43264 ≡ 192 mod 673

64: 590⁶⁴=590³²⁺³²=590³²⋅590³² ≡ 192⋅192=36864 ≡ 522 mod 673

128: 590¹²⁸=590⁶⁴⁺⁶⁴=590⁶⁴⋅590⁶⁴ ≡ 522⋅522=272484 ≡ 592 mod 673

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

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

197 = 128+64+4+1

271¹⁹⁷

= 271^128+64+4+1

= 271¹²⁸⋅271⁶⁴⋅271⁴⋅271¹

≡ 329 ⋅ 321 ⋅ 208 ⋅ 271 mod 347
≡ 105609 ⋅ 208 ⋅ 271 mod 347 ≡ 121 ⋅ 208 ⋅ 271 mod 347
≡ 25168 ⋅ 271 mod 347 ≡ 184 ⋅ 271 mod 347
≡ 49864 mod 347 ≡ 243 mod 347

Es gilt also: 271¹⁹⁷ ≡ 243 mod 347

Berechnung des größten gemeinsamen Teilers von 59 und 38

=>59	= 1⋅38 + 21
=>38	= 1⋅21 + 17
=>21	= 1⋅17 + 4
=>17	= 4⋅4 + 1
=>4	= 4⋅1 + 0

also gilt: ggt(59,38)=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-4⋅4
4= 21-1⋅17	eingesetzt in die Zeile drüber:	1	= 1⋅17 -4⋅(21 -1⋅ 17) = 1⋅17 -4⋅21 +4⋅ 17) = -4⋅21 +5⋅ 17 (=1)
17= 38-1⋅21	eingesetzt in die Zeile drüber:	1	= -4⋅21 +5⋅(38 -1⋅ 21) = -4⋅21 +5⋅38 -5⋅ 21) = 5⋅38 -9⋅ 21 (=1)
21= 59-1⋅38	eingesetzt in die Zeile drüber:	1	= 5⋅38 -9⋅(59 -1⋅ 38) = 5⋅38 -9⋅59 +9⋅ 38) = -9⋅59 +14⋅ 38 (=1)

Es gilt also: ggt(59,38)=1 = -9⋅59 +14⋅38

oder wenn man -9⋅59 auf die linke Seite bringt:

1 +9⋅59 = +14⋅38

Es gilt also: 14⋅38 = 9⋅59 +1

Somit 14⋅38 = 1 mod 59

14 ist also das Inverse von 38 mod 59