Um längere Rechnungen zu vermeiden, rechnen wir:

(162 + 1203) mod 4 ≡ (162 mod 4 + 1203 mod 4) mod 4.

162 mod 4 ≡ 2 mod 4 kann man relativ leicht bestimmen, weil ja 162 = 160+2 = 4 ⋅ 40 +2.

1203 mod 4 ≡ 3 mod 4 kann man relativ leicht bestimmen, weil ja 1203 = 1200+3 = 4 ⋅ 300 +3.

Somit gilt:

(162 + 1203) mod 4 ≡ (2 + 3) mod 4 ≡ 5 mod 4 ≡ 1 mod 4.

Um längere Rechnungen zu vermeiden, rechnen wir:

(21 ⋅ 80) mod 6 ≡ (21 mod 6 ⋅ 80 mod 6) mod 6.

21 mod 6 ≡ 3 mod 6 kann man relativ leicht bestimmen, weil ja 21 = 18 + 3 = 3 ⋅ 6 + 3 ist.

80 mod 6 ≡ 2 mod 6 kann man relativ leicht bestimmen, weil ja 80 = 78 + 2 = 13 ⋅ 6 + 2 ist.

Somit gilt:

(21 ⋅ 80) mod 6 ≡ (3 ⋅ 2) mod 6 ≡ 6 mod 6 ≡ 0 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: 181¹=181

2: 181²=181¹⁺¹=181¹⋅181¹ ≡ 181⋅181=32761 ≡ 301 mod 541

4: 181⁴=181²⁺²=181²⋅181² ≡ 301⋅301=90601 ≡ 254 mod 541

8: 181⁸=181⁴⁺⁴=181⁴⋅181⁴ ≡ 254⋅254=64516 ≡ 137 mod 541

16: 181¹⁶=181⁸⁺⁸=181⁸⋅181⁸ ≡ 137⋅137=18769 ≡ 375 mod 541

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

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

221 = 128+64+16+8+4+1

794²²¹

= 794^{128+64+16+8+4+1}

= 794¹²⁸⋅794⁶⁴⋅794¹⁶⋅794⁸⋅794⁴⋅794¹

≡ 177 ⋅ 524 ⋅ 169 ⋅ 816 ⋅ 135 ⋅ 794 mod 829
≡ 92748 ⋅ 169 ⋅ 816 ⋅ 135 ⋅ 794 mod 829 ≡ 729 ⋅ 169 ⋅ 816 ⋅ 135 ⋅ 794 mod 829
≡ 123201 ⋅ 816 ⋅ 135 ⋅ 794 mod 829 ≡ 509 ⋅ 816 ⋅ 135 ⋅ 794 mod 829
≡ 415344 ⋅ 135 ⋅ 794 mod 829 ≡ 15 ⋅ 135 ⋅ 794 mod 829
≡ 2025 ⋅ 794 mod 829 ≡ 367 ⋅ 794 mod 829
≡ 291398 mod 829 ≡ 419 mod 829

Es gilt also: 794²²¹ ≡ 419 mod 829

Berechnung des größten gemeinsamen Teilers von 67 und 30

=>67	= 2⋅30 + 7
=>30	= 4⋅7 + 2
=>7	= 3⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(67,30)=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= 7-3⋅2
2= 30-4⋅7	eingesetzt in die Zeile drüber:	1	= 1⋅7 -3⋅(30 -4⋅ 7) = 1⋅7 -3⋅30 +12⋅ 7) = -3⋅30 +13⋅ 7 (=1)
7= 67-2⋅30	eingesetzt in die Zeile drüber:	1	= -3⋅30 +13⋅(67 -2⋅ 30) = -3⋅30 +13⋅67 -26⋅ 30) = 13⋅67 -29⋅ 30 (=1)

Es gilt also: ggt(67,30)=1 = 13⋅67 -29⋅30

oder wenn man 13⋅67 auf die linke Seite bringt:

1 -13⋅67 = -29⋅30

-29⋅30 = -13⋅67 + 1 |+67⋅30

-29⋅30 + 67⋅30 = -13⋅67 + 67⋅30 + 1

(-29 + 67) ⋅ 30 = (-13 + 30) ⋅ 67 + 1

38⋅30 = 17⋅67 + 1

Es gilt also: 38⋅30 = 17⋅67 +1

Somit 38⋅30 = 1 mod 67

38 ist also das Inverse von 30 mod 67