Um längere Rechnungen zu vermeiden, rechnen wir:

(93 + 3002) mod 3 ≡ (93 mod 3 + 3002 mod 3) mod 3.

93 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 93 = 90+3 = 3 ⋅ 30 +3.

3002 mod 3 ≡ 2 mod 3 kann man relativ leicht bestimmen, weil ja 3002 = 3000+2 = 3 ⋅ 1000 +2.

Somit gilt:

(93 + 3002) mod 3 ≡ (0 + 2) mod 3 ≡ 2 mod 3.

Um längere Rechnungen zu vermeiden, rechnen wir:

(17 ⋅ 56) mod 6 ≡ (17 mod 6 ⋅ 56 mod 6) mod 6.

17 mod 6 ≡ 5 mod 6 kann man relativ leicht bestimmen, weil ja 17 = 12 + 5 = 2 ⋅ 6 + 5 ist.

56 mod 6 ≡ 2 mod 6 kann man relativ leicht bestimmen, weil ja 56 = 54 + 2 = 9 ⋅ 6 + 2 ist.

Somit gilt:

(17 ⋅ 56) mod 6 ≡ (5 ⋅ 2) mod 6 ≡ 10 mod 6 ≡ 4 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: 568¹=568

2: 568²=568¹⁺¹=568¹⋅568¹ ≡ 568⋅568=322624 ≡ 164 mod 701

4: 568⁴=568²⁺²=568²⋅568² ≡ 164⋅164=26896 ≡ 258 mod 701

8: 568⁸=568⁴⁺⁴=568⁴⋅568⁴ ≡ 258⋅258=66564 ≡ 670 mod 701

16: 568¹⁶=568⁸⁺⁸=568⁸⋅568⁸ ≡ 670⋅670=448900 ≡ 260 mod 701

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

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

229 = 128+64+32+4+1

361²²⁹

= 361^{128+64+32+4+1}

= 361¹²⁸⋅361⁶⁴⋅361³²⋅361⁴⋅361¹

≡ 845 ⋅ 344 ⋅ 105 ⋅ 125 ⋅ 361 mod 971
≡ 290680 ⋅ 105 ⋅ 125 ⋅ 361 mod 971 ≡ 351 ⋅ 105 ⋅ 125 ⋅ 361 mod 971
≡ 36855 ⋅ 125 ⋅ 361 mod 971 ≡ 928 ⋅ 125 ⋅ 361 mod 971
≡ 116000 ⋅ 361 mod 971 ≡ 451 ⋅ 361 mod 971
≡ 162811 mod 971 ≡ 654 mod 971

Es gilt also: 361²²⁹ ≡ 654 mod 971

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

=>67	= 1⋅42 + 25
=>42	= 1⋅25 + 17
=>25	= 1⋅17 + 8
=>17	= 2⋅8 + 1
=>8	= 8⋅1 + 0

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

Es gilt also: ggt(67,42)=1 = -5⋅67 +8⋅42

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

1 +5⋅67 = +8⋅42

Es gilt also: 8⋅42 = 5⋅67 +1

Somit 8⋅42 = 1 mod 67

8 ist also das Inverse von 42 mod 67