Um längere Rechnungen zu vermeiden, rechnen wir:

(5999 + 597) mod 3 ≡ (5999 mod 3 + 597 mod 3) mod 3.

5999 mod 3 ≡ 2 mod 3 kann man relativ leicht bestimmen, weil ja 5999 = 6000-1 = 3 ⋅ 2000 -1 = 3 ⋅ 2000 - 3 + 2.

597 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 597 = 600-3 = 3 ⋅ 200 -3 = 3 ⋅ 200 - 3 + 0.

Somit gilt:

(5999 + 597) mod 3 ≡ (2 + 0) mod 3 ≡ 2 mod 3.

Um längere Rechnungen zu vermeiden, rechnen wir:

(63 ⋅ 70) mod 10 ≡ (63 mod 10 ⋅ 70 mod 10) mod 10.

63 mod 10 ≡ 3 mod 10 kann man relativ leicht bestimmen, weil ja 63 = 60 + 3 = 6 ⋅ 10 + 3 ist.

70 mod 10 ≡ 0 mod 10 kann man relativ leicht bestimmen, weil ja 70 = 70 + 0 = 7 ⋅ 10 + 0 ist.

Somit gilt:

(63 ⋅ 70) mod 10 ≡ (3 ⋅ 0) mod 10 ≡ 0 mod 10.

Die 32 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: 183¹=183

2: 183²=183¹⁺¹=183¹⋅183¹ ≡ 183⋅183=33489 ≡ 79 mod 257

4: 183⁴=183²⁺²=183²⋅183² ≡ 79⋅79=6241 ≡ 73 mod 257

8: 183⁸=183⁴⁺⁴=183⁴⋅183⁴ ≡ 73⋅73=5329 ≡ 189 mod 257

16: 183¹⁶=183⁸⁺⁸=183⁸⋅183⁸ ≡ 189⋅189=35721 ≡ 255 mod 257

32: 183³²=183¹⁶⁺¹⁶=183¹⁶⋅183¹⁶ ≡ 255⋅255=65025 ≡ 4 mod 257

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

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

213 = 128+64+16+4+1

358²¹³

= 358^{128+64+16+4+1}

= 358¹²⁸⋅358⁶⁴⋅358¹⁶⋅358⁴⋅358¹

≡ 333 ⋅ 618 ⋅ 450 ⋅ 292 ⋅ 358 mod 673
≡ 205794 ⋅ 450 ⋅ 292 ⋅ 358 mod 673 ≡ 529 ⋅ 450 ⋅ 292 ⋅ 358 mod 673
≡ 238050 ⋅ 292 ⋅ 358 mod 673 ≡ 481 ⋅ 292 ⋅ 358 mod 673
≡ 140452 ⋅ 358 mod 673 ≡ 468 ⋅ 358 mod 673
≡ 167544 mod 673 ≡ 640 mod 673

Es gilt also: 358²¹³ ≡ 640 mod 673

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

=>67	= 1⋅51 + 16
=>51	= 3⋅16 + 3
=>16	= 5⋅3 + 1
=>3	= 3⋅1 + 0

also gilt: ggt(67,51)=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= 16-5⋅3
3= 51-3⋅16	eingesetzt in die Zeile drüber:	1	= 1⋅16 -5⋅(51 -3⋅ 16) = 1⋅16 -5⋅51 +15⋅ 16) = -5⋅51 +16⋅ 16 (=1)
16= 67-1⋅51	eingesetzt in die Zeile drüber:	1	= -5⋅51 +16⋅(67 -1⋅ 51) = -5⋅51 +16⋅67 -16⋅ 51) = 16⋅67 -21⋅ 51 (=1)

Es gilt also: ggt(67,51)=1 = 16⋅67 -21⋅51

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

1 -16⋅67 = -21⋅51

-21⋅51 = -16⋅67 + 1 |+67⋅51

-21⋅51 + 67⋅51 = -16⋅67 + 67⋅51 + 1

(-21 + 67) ⋅ 51 = (-16 + 51) ⋅ 67 + 1

46⋅51 = 35⋅67 + 1

Es gilt also: 46⋅51 = 35⋅67 +1

Somit 46⋅51 = 1 mod 67

46 ist also das Inverse von 51 mod 67