Um längere Rechnungen zu vermeiden, rechnen wir:

(12000 + 1202) mod 3 ≡ (12000 mod 3 + 1202 mod 3) mod 3.

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

1202 mod 3 ≡ 2 mod 3 kann man relativ leicht bestimmen, weil ja 1202 = 1200+2 = 3 ⋅ 400 +2.

Somit gilt:

(12000 + 1202) mod 3 ≡ (0 + 2) mod 3 ≡ 2 mod 3.

Um längere Rechnungen zu vermeiden, rechnen wir:

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

22 mod 8 ≡ 6 mod 8 kann man relativ leicht bestimmen, weil ja 22 = 16 + 6 = 2 ⋅ 8 + 6 ist.

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

Somit gilt:

(22 ⋅ 88) mod 8 ≡ (6 ⋅ 0) mod 8 ≡ 0 mod 8.

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

2: 210²=210¹⁺¹=210¹⋅210¹ ≡ 210⋅210=44100 ≡ 136 mod 379

4: 210⁴=210²⁺²=210²⋅210² ≡ 136⋅136=18496 ≡ 304 mod 379

8: 210⁸=210⁴⁺⁴=210⁴⋅210⁴ ≡ 304⋅304=92416 ≡ 319 mod 379

16: 210¹⁶=210⁸⁺⁸=210⁸⋅210⁸ ≡ 319⋅319=101761 ≡ 189 mod 379

32: 210³²=210¹⁶⁺¹⁶=210¹⁶⋅210¹⁶ ≡ 189⋅189=35721 ≡ 95 mod 379

64: 210⁶⁴=210³²⁺³²=210³²⋅210³² ≡ 95⋅95=9025 ≡ 308 mod 379

128: 210¹²⁸=210⁶⁴⁺⁶⁴=210⁶⁴⋅210⁶⁴ ≡ 308⋅308=94864 ≡ 114 mod 379

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

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

93 = 64+16+8+4+1

547⁹³

= 547^64+16+8+4+1

= 547⁶⁴⋅547¹⁶⋅547⁸⋅547⁴⋅547¹

≡ 106 ⋅ 127 ⋅ 392 ⋅ 433 ⋅ 547 mod 839
≡ 13462 ⋅ 392 ⋅ 433 ⋅ 547 mod 839 ≡ 38 ⋅ 392 ⋅ 433 ⋅ 547 mod 839
≡ 14896 ⋅ 433 ⋅ 547 mod 839 ≡ 633 ⋅ 433 ⋅ 547 mod 839
≡ 274089 ⋅ 547 mod 839 ≡ 575 ⋅ 547 mod 839
≡ 314525 mod 839 ≡ 739 mod 839

Es gilt also: 547⁹³ ≡ 739 mod 839

Berechnung des größten gemeinsamen Teilers von 53 und 19

=>53	= 2⋅19 + 15
=>19	= 1⋅15 + 4
=>15	= 3⋅4 + 3
=>4	= 1⋅3 + 1
=>3	= 3⋅1 + 0

also gilt: ggt(53,19)=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= 4-1⋅3
3= 15-3⋅4	eingesetzt in die Zeile drüber:	1	= 1⋅4 -1⋅(15 -3⋅ 4) = 1⋅4 -1⋅15 +3⋅ 4) = -1⋅15 +4⋅ 4 (=1)
4= 19-1⋅15	eingesetzt in die Zeile drüber:	1	= -1⋅15 +4⋅(19 -1⋅ 15) = -1⋅15 +4⋅19 -4⋅ 15) = 4⋅19 -5⋅ 15 (=1)
15= 53-2⋅19	eingesetzt in die Zeile drüber:	1	= 4⋅19 -5⋅(53 -2⋅ 19) = 4⋅19 -5⋅53 +10⋅ 19) = -5⋅53 +14⋅ 19 (=1)

Es gilt also: ggt(53,19)=1 = -5⋅53 +14⋅19

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

1 +5⋅53 = +14⋅19

Es gilt also: 14⋅19 = 5⋅53 +1

Somit 14⋅19 = 1 mod 53

14 ist also das Inverse von 19 mod 53