Um längere Rechnungen zu vermeiden, rechnen wir:

(806 + 3205) mod 8 ≡ (806 mod 8 + 3205 mod 8) mod 8.

806 mod 8 ≡ 6 mod 8 kann man relativ leicht bestimmen, weil ja 806 = 800+6 = 8 ⋅ 100 +6.

3205 mod 8 ≡ 5 mod 8 kann man relativ leicht bestimmen, weil ja 3205 = 3200+5 = 8 ⋅ 400 +5.

Somit gilt:

(806 + 3205) mod 8 ≡ (6 + 5) mod 8 ≡ 11 mod 8 ≡ 3 mod 8.

Um längere Rechnungen zu vermeiden, rechnen wir:

(49 ⋅ 16) mod 3 ≡ (49 mod 3 ⋅ 16 mod 3) mod 3.

49 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 49 = 48 + 1 = 16 ⋅ 3 + 1 ist.

16 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 16 = 15 + 1 = 5 ⋅ 3 + 1 ist.

Somit gilt:

(49 ⋅ 16) mod 3 ≡ (1 ⋅ 1) mod 3 ≡ 1 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: 274¹=274

2: 274²=274¹⁺¹=274¹⋅274¹ ≡ 274⋅274=75076 ≡ 138 mod 421

4: 274⁴=274²⁺²=274²⋅274² ≡ 138⋅138=19044 ≡ 99 mod 421

8: 274⁸=274⁴⁺⁴=274⁴⋅274⁴ ≡ 99⋅99=9801 ≡ 118 mod 421

16: 274¹⁶=274⁸⁺⁸=274⁸⋅274⁸ ≡ 118⋅118=13924 ≡ 31 mod 421

32: 274³²=274¹⁶⁺¹⁶=274¹⁶⋅274¹⁶ ≡ 31⋅31=961 ≡ 119 mod 421

64: 274⁶⁴=274³²⁺³²=274³²⋅274³² ≡ 119⋅119=14161 ≡ 268 mod 421

128: 274¹²⁸=274⁶⁴⁺⁶⁴=274⁶⁴⋅274⁶⁴ ≡ 268⋅268=71824 ≡ 254 mod 421

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

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

219 = 128+64+16+8+2+1

231²¹⁹

= 231^{128+64+16+8+2+1}

= 231¹²⁸⋅231⁶⁴⋅231¹⁶⋅231⁸⋅231²⋅231¹

≡ 357 ⋅ 169 ⋅ 44 ⋅ 584 ⋅ 158 ⋅ 231 mod 641
≡ 60333 ⋅ 44 ⋅ 584 ⋅ 158 ⋅ 231 mod 641 ≡ 79 ⋅ 44 ⋅ 584 ⋅ 158 ⋅ 231 mod 641
≡ 3476 ⋅ 584 ⋅ 158 ⋅ 231 mod 641 ≡ 271 ⋅ 584 ⋅ 158 ⋅ 231 mod 641
≡ 158264 ⋅ 158 ⋅ 231 mod 641 ≡ 578 ⋅ 158 ⋅ 231 mod 641
≡ 91324 ⋅ 231 mod 641 ≡ 302 ⋅ 231 mod 641
≡ 69762 mod 641 ≡ 534 mod 641

Es gilt also: 231²¹⁹ ≡ 534 mod 641

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

=>53	= 1⋅47 + 6
=>47	= 7⋅6 + 5
=>6	= 1⋅5 + 1
=>5	= 5⋅1 + 0

also gilt: ggt(53,47)=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= 6-1⋅5
5= 47-7⋅6	eingesetzt in die Zeile drüber:	1	= 1⋅6 -1⋅(47 -7⋅ 6) = 1⋅6 -1⋅47 +7⋅ 6) = -1⋅47 +8⋅ 6 (=1)
6= 53-1⋅47	eingesetzt in die Zeile drüber:	1	= -1⋅47 +8⋅(53 -1⋅ 47) = -1⋅47 +8⋅53 -8⋅ 47) = 8⋅53 -9⋅ 47 (=1)

Es gilt also: ggt(53,47)=1 = 8⋅53 -9⋅47

oder wenn man 8⋅53 auf die linke Seite bringt:

1 -8⋅53 = -9⋅47

-9⋅47 = -8⋅53 + 1 |+53⋅47

-9⋅47 + 53⋅47 = -8⋅53 + 53⋅47 + 1

(-9 + 53) ⋅ 47 = (-8 + 47) ⋅ 53 + 1

44⋅47 = 39⋅53 + 1

Es gilt also: 44⋅47 = 39⋅53 +1

Somit 44⋅47 = 1 mod 53

44 ist also das Inverse von 47 mod 53