Um längere Rechnungen zu vermeiden, rechnen wir:

(3006 - 5998) mod 6 ≡ (3006 mod 6 - 5998 mod 6) mod 6.

3006 mod 6 ≡ 0 mod 6 kann man relativ leicht bestimmen, weil ja 3006 = 3000+6 = 6 ⋅ 500 +6.

5998 mod 6 ≡ 4 mod 6 kann man relativ leicht bestimmen, weil ja 5998 = 6000-2 = 6 ⋅ 1000 -2 = 6 ⋅ 1000 - 6 + 4.

Somit gilt:

(3006 - 5998) mod 6 ≡ (0 - 4) mod 6 ≡ -4 mod 6 ≡ 2 mod 6.

Um längere Rechnungen zu vermeiden, rechnen wir:

(43 ⋅ 43) mod 6 ≡ (43 mod 6 ⋅ 43 mod 6) mod 6.

43 mod 6 ≡ 1 mod 6 kann man relativ leicht bestimmen, weil ja 43 = 42 + 1 = 7 ⋅ 6 + 1 ist.

43 mod 6 ≡ 1 mod 6 kann man relativ leicht bestimmen, weil ja 43 = 42 + 1 = 7 ⋅ 6 + 1 ist.

Somit gilt:

(43 ⋅ 43) mod 6 ≡ (1 ⋅ 1) mod 6 ≡ 1 mod 6.

Die 16 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: 199¹=199

2: 199²=199¹⁺¹=199¹⋅199¹ ≡ 199⋅199=39601 ≡ 163 mod 313

4: 199⁴=199²⁺²=199²⋅199² ≡ 163⋅163=26569 ≡ 277 mod 313

8: 199⁸=199⁴⁺⁴=199⁴⋅199⁴ ≡ 277⋅277=76729 ≡ 44 mod 313

16: 199¹⁶=199⁸⁺⁸=199⁸⋅199⁸ ≡ 44⋅44=1936 ≡ 58 mod 313

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

464²¹⁹

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

= 464¹²⁸⋅464⁶⁴⋅464¹⁶⋅464⁸⋅464²⋅464¹

≡ 41 ⋅ 414 ⋅ 782 ⋅ 505 ⋅ 106 ⋅ 464 mod 797
≡ 16974 ⋅ 782 ⋅ 505 ⋅ 106 ⋅ 464 mod 797 ≡ 237 ⋅ 782 ⋅ 505 ⋅ 106 ⋅ 464 mod 797
≡ 185334 ⋅ 505 ⋅ 106 ⋅ 464 mod 797 ≡ 430 ⋅ 505 ⋅ 106 ⋅ 464 mod 797
≡ 217150 ⋅ 106 ⋅ 464 mod 797 ≡ 366 ⋅ 106 ⋅ 464 mod 797
≡ 38796 ⋅ 464 mod 797 ≡ 540 ⋅ 464 mod 797
≡ 250560 mod 797 ≡ 302 mod 797

Es gilt also: 464²¹⁹ ≡ 302 mod 797

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

=>53	= 1⋅28 + 25
=>28	= 1⋅25 + 3
=>25	= 8⋅3 + 1
=>3	= 3⋅1 + 0

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

Es gilt also: ggt(53,28)=1 = 9⋅53 -17⋅28

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

1 -9⋅53 = -17⋅28

-17⋅28 = -9⋅53 + 1 |+53⋅28

-17⋅28 + 53⋅28 = -9⋅53 + 53⋅28 + 1

(-17 + 53) ⋅ 28 = (-9 + 28) ⋅ 53 + 1

36⋅28 = 19⋅53 + 1

Es gilt also: 36⋅28 = 19⋅53 +1

Somit 36⋅28 = 1 mod 53

36 ist also das Inverse von 28 mod 53