Um längere Rechnungen zu vermeiden, rechnen wir:

(18005 - 18004) mod 6 ≡ (18005 mod 6 - 18004 mod 6) mod 6.

18005 mod 6 ≡ 5 mod 6 kann man relativ leicht bestimmen, weil ja 18005 = 18000+5 = 6 ⋅ 3000 +5.

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

Somit gilt:

(18005 - 18004) mod 6 ≡ (5 - 4) mod 6 ≡ 1 mod 6.

Um längere Rechnungen zu vermeiden, rechnen wir:

(65 ⋅ 74) mod 3 ≡ (65 mod 3 ⋅ 74 mod 3) mod 3.

65 mod 3 ≡ 2 mod 3 kann man relativ leicht bestimmen, weil ja 65 = 63 + 2 = 21 ⋅ 3 + 2 ist.

74 mod 3 ≡ 2 mod 3 kann man relativ leicht bestimmen, weil ja 74 = 72 + 2 = 24 ⋅ 3 + 2 ist.

Somit gilt:

(65 ⋅ 74) mod 3 ≡ (2 ⋅ 2) mod 3 ≡ 4 mod 3 ≡ 1 mod 3.

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

2: 232²=232¹⁺¹=232¹⋅232¹ ≡ 232⋅232=53824 ≡ 168 mod 353

4: 232⁴=232²⁺²=232²⋅232² ≡ 168⋅168=28224 ≡ 337 mod 353

8: 232⁸=232⁴⁺⁴=232⁴⋅232⁴ ≡ 337⋅337=113569 ≡ 256 mod 353

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

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

247 = 128+64+32+16+4+2+1

433²⁴⁷

= 433^{128+64+32+16+4+2+1}

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

≡ 264 ⋅ 259 ⋅ 537 ⋅ 449 ⋅ 565 ⋅ 524 ⋅ 433 mod 613
≡ 68376 ⋅ 537 ⋅ 449 ⋅ 565 ⋅ 524 ⋅ 433 mod 613 ≡ 333 ⋅ 537 ⋅ 449 ⋅ 565 ⋅ 524 ⋅ 433 mod 613
≡ 178821 ⋅ 449 ⋅ 565 ⋅ 524 ⋅ 433 mod 613 ≡ 438 ⋅ 449 ⋅ 565 ⋅ 524 ⋅ 433 mod 613
≡ 196662 ⋅ 565 ⋅ 524 ⋅ 433 mod 613 ≡ 502 ⋅ 565 ⋅ 524 ⋅ 433 mod 613
≡ 283630 ⋅ 524 ⋅ 433 mod 613 ≡ 424 ⋅ 524 ⋅ 433 mod 613
≡ 222176 ⋅ 433 mod 613 ≡ 270 ⋅ 433 mod 613
≡ 116910 mod 613 ≡ 440 mod 613

Es gilt also: 433²⁴⁷ ≡ 440 mod 613

Berechnung des größten gemeinsamen Teilers von 61 und 23

=>61	= 2⋅23 + 15
=>23	= 1⋅15 + 8
=>15	= 1⋅8 + 7
=>8	= 1⋅7 + 1
=>7	= 7⋅1 + 0

also gilt: ggt(61,23)=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= 8-1⋅7
7= 15-1⋅8	eingesetzt in die Zeile drüber:	1	= 1⋅8 -1⋅(15 -1⋅ 8) = 1⋅8 -1⋅15 +1⋅ 8) = -1⋅15 +2⋅ 8 (=1)
8= 23-1⋅15	eingesetzt in die Zeile drüber:	1	= -1⋅15 +2⋅(23 -1⋅ 15) = -1⋅15 +2⋅23 -2⋅ 15) = 2⋅23 -3⋅ 15 (=1)
15= 61-2⋅23	eingesetzt in die Zeile drüber:	1	= 2⋅23 -3⋅(61 -2⋅ 23) = 2⋅23 -3⋅61 +6⋅ 23) = -3⋅61 +8⋅ 23 (=1)

Es gilt also: ggt(61,23)=1 = -3⋅61 +8⋅23

oder wenn man -3⋅61 auf die linke Seite bringt:

1 +3⋅61 = +8⋅23

Es gilt also: 8⋅23 = 3⋅61 +1

Somit 8⋅23 = 1 mod 61

8 ist also das Inverse von 23 mod 61