Um längere Rechnungen zu vermeiden, rechnen wir:

(17998 - 1795) mod 6 ≡ (17998 mod 6 - 1795 mod 6) mod 6.

17998 mod 6 ≡ 4 mod 6 kann man relativ leicht bestimmen, weil ja 17998 = 18000-2 = 6 ⋅ 3000 -2 = 6 ⋅ 3000 - 6 + 4.

1795 mod 6 ≡ 1 mod 6 kann man relativ leicht bestimmen, weil ja 1795 = 1800-5 = 6 ⋅ 300 -5 = 6 ⋅ 300 - 6 + 1.

Somit gilt:

(17998 - 1795) mod 6 ≡ (4 - 1) mod 6 ≡ 3 mod 6.

Um längere Rechnungen zu vermeiden, rechnen wir:

(62 ⋅ 36) mod 10 ≡ (62 mod 10 ⋅ 36 mod 10) mod 10.

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

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

Somit gilt:

(62 ⋅ 36) mod 10 ≡ (2 ⋅ 6) mod 10 ≡ 12 mod 10 ≡ 2 mod 10.

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: 229¹=229

2: 229²=229¹⁺¹=229¹⋅229¹ ≡ 229⋅229=52441 ≡ 230 mod 479

4: 229⁴=229²⁺²=229²⋅229² ≡ 230⋅230=52900 ≡ 210 mod 479

8: 229⁸=229⁴⁺⁴=229⁴⋅229⁴ ≡ 210⋅210=44100 ≡ 32 mod 479

16: 229¹⁶=229⁸⁺⁸=229⁸⋅229⁸ ≡ 32⋅32=1024 ≡ 66 mod 479

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

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

125 = 64+32+16+8+4+1

456¹²⁵

= 456^{64+32+16+8+4+1}

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

≡ 196 ⋅ 14 ⋅ 484 ⋅ 22 ⋅ 608 ⋅ 456 mod 677
≡ 2744 ⋅ 484 ⋅ 22 ⋅ 608 ⋅ 456 mod 677 ≡ 36 ⋅ 484 ⋅ 22 ⋅ 608 ⋅ 456 mod 677
≡ 17424 ⋅ 22 ⋅ 608 ⋅ 456 mod 677 ≡ 499 ⋅ 22 ⋅ 608 ⋅ 456 mod 677
≡ 10978 ⋅ 608 ⋅ 456 mod 677 ≡ 146 ⋅ 608 ⋅ 456 mod 677
≡ 88768 ⋅ 456 mod 677 ≡ 81 ⋅ 456 mod 677
≡ 36936 mod 677 ≡ 378 mod 677

Es gilt also: 456¹²⁵ ≡ 378 mod 677

Berechnung des größten gemeinsamen Teilers von 101 und 94

=>101	= 1⋅94 + 7
=>94	= 13⋅7 + 3
=>7	= 2⋅3 + 1
=>3	= 3⋅1 + 0

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

Es gilt also: ggt(101,94)=1 = 27⋅101 -29⋅94

oder wenn man 27⋅101 auf die linke Seite bringt:

1 -27⋅101 = -29⋅94

-29⋅94 = -27⋅101 + 1 |+101⋅94

-29⋅94 + 101⋅94 = -27⋅101 + 101⋅94 + 1

(-29 + 101) ⋅ 94 = (-27 + 94) ⋅ 101 + 1

72⋅94 = 67⋅101 + 1

Es gilt also: 72⋅94 = 67⋅101 +1

Somit 72⋅94 = 1 mod 101

72 ist also das Inverse von 94 mod 101