Um längere Rechnungen zu vermeiden, rechnen wir:

(23997 + 298) mod 6 ≡ (23997 mod 6 + 298 mod 6) mod 6.

23997 mod 6 ≡ 3 mod 6 kann man relativ leicht bestimmen, weil ja 23997 = 24000-3 = 6 ⋅ 4000 -3 = 6 ⋅ 4000 - 6 + 3.

298 mod 6 ≡ 4 mod 6 kann man relativ leicht bestimmen, weil ja 298 = 300-2 = 6 ⋅ 50 -2 = 6 ⋅ 50 - 6 + 4.

Somit gilt:

(23997 + 298) mod 6 ≡ (3 + 4) mod 6 ≡ 7 mod 6 ≡ 1 mod 6.

Um längere Rechnungen zu vermeiden, rechnen wir:

(58 ⋅ 33) mod 11 ≡ (58 mod 11 ⋅ 33 mod 11) mod 11.

58 mod 11 ≡ 3 mod 11 kann man relativ leicht bestimmen, weil ja 58 = 55 + 3 = 5 ⋅ 11 + 3 ist.

33 mod 11 ≡ 0 mod 11 kann man relativ leicht bestimmen, weil ja 33 = 33 + 0 = 3 ⋅ 11 + 0 ist.

Somit gilt:

(58 ⋅ 33) mod 11 ≡ (3 ⋅ 0) mod 11 ≡ 0 mod 11.

Die 8 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: 520¹=520

2: 520²=520¹⁺¹=520¹⋅520¹ ≡ 520⋅520=270400 ≡ 539 mod 641

4: 520⁴=520²⁺²=520²⋅520² ≡ 539⋅539=290521 ≡ 148 mod 641

8: 520⁸=520⁴⁺⁴=520⁴⋅520⁴ ≡ 148⋅148=21904 ≡ 110 mod 641

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

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

111 = 64+32+8+4+2+1

420¹¹¹

= 420^{64+32+8+4+2+1}

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

≡ 222 ⋅ 116 ⋅ 504 ⋅ 356 ⋅ 286 ⋅ 420 mod 509
≡ 25752 ⋅ 504 ⋅ 356 ⋅ 286 ⋅ 420 mod 509 ≡ 302 ⋅ 504 ⋅ 356 ⋅ 286 ⋅ 420 mod 509
≡ 152208 ⋅ 356 ⋅ 286 ⋅ 420 mod 509 ≡ 17 ⋅ 356 ⋅ 286 ⋅ 420 mod 509
≡ 6052 ⋅ 286 ⋅ 420 mod 509 ≡ 453 ⋅ 286 ⋅ 420 mod 509
≡ 129558 ⋅ 420 mod 509 ≡ 272 ⋅ 420 mod 509
≡ 114240 mod 509 ≡ 224 mod 509

Es gilt also: 420¹¹¹ ≡ 224 mod 509

Berechnung des größten gemeinsamen Teilers von 71 und 55

=>71	= 1⋅55 + 16
=>55	= 3⋅16 + 7
=>16	= 2⋅7 + 2
=>7	= 3⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(71,55)=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= 16-2⋅7	eingesetzt in die Zeile drüber:	1	= 1⋅7 -3⋅(16 -2⋅ 7) = 1⋅7 -3⋅16 +6⋅ 7) = -3⋅16 +7⋅ 7 (=1)
7= 55-3⋅16	eingesetzt in die Zeile drüber:	1	= -3⋅16 +7⋅(55 -3⋅ 16) = -3⋅16 +7⋅55 -21⋅ 16) = 7⋅55 -24⋅ 16 (=1)
16= 71-1⋅55	eingesetzt in die Zeile drüber:	1	= 7⋅55 -24⋅(71 -1⋅ 55) = 7⋅55 -24⋅71 +24⋅ 55) = -24⋅71 +31⋅ 55 (=1)

Es gilt also: ggt(71,55)=1 = -24⋅71 +31⋅55

oder wenn man -24⋅71 auf die linke Seite bringt:

1 +24⋅71 = +31⋅55

Es gilt also: 31⋅55 = 24⋅71 +1

Somit 31⋅55 = 1 mod 71

31 ist also das Inverse von 55 mod 71