Um längere Rechnungen zu vermeiden, rechnen wir:

(6004 - 122) mod 6 ≡ (6004 mod 6 - 122 mod 6) mod 6.

6004 mod 6 ≡ 4 mod 6 kann man relativ leicht bestimmen, weil ja 6004 = 6000+4 = 6 ⋅ 1000 +4.

122 mod 6 ≡ 2 mod 6 kann man relativ leicht bestimmen, weil ja 122 = 120+2 = 6 ⋅ 20 +2.

Somit gilt:

(6004 - 122) mod 6 ≡ (4 - 2) mod 6 ≡ 2 mod 6.

Um längere Rechnungen zu vermeiden, rechnen wir:

(94 ⋅ 20) mod 6 ≡ (94 mod 6 ⋅ 20 mod 6) mod 6.

94 mod 6 ≡ 4 mod 6 kann man relativ leicht bestimmen, weil ja 94 = 90 + 4 = 15 ⋅ 6 + 4 ist.

20 mod 6 ≡ 2 mod 6 kann man relativ leicht bestimmen, weil ja 20 = 18 + 2 = 3 ⋅ 6 + 2 ist.

Somit gilt:

(94 ⋅ 20) mod 6 ≡ (4 ⋅ 2) mod 6 ≡ 8 mod 6 ≡ 2 mod 6.

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

2: 463²=463¹⁺¹=463¹⋅463¹ ≡ 463⋅463=214369 ≡ 381 mod 877

4: 463⁴=463²⁺²=463²⋅463² ≡ 381⋅381=145161 ≡ 456 mod 877

8: 463⁸=463⁴⁺⁴=463⁴⋅463⁴ ≡ 456⋅456=207936 ≡ 87 mod 877

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

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

223 = 128+64+16+8+4+2+1

531²²³

= 531^{128+64+16+8+4+2+1}

= 531¹²⁸⋅531⁶⁴⋅531¹⁶⋅531⁸⋅531⁴⋅531²⋅531¹

≡ 263 ⋅ 45 ⋅ 180 ⋅ 394 ⋅ 800 ⋅ 41 ⋅ 531 mod 881
≡ 11835 ⋅ 180 ⋅ 394 ⋅ 800 ⋅ 41 ⋅ 531 mod 881 ≡ 382 ⋅ 180 ⋅ 394 ⋅ 800 ⋅ 41 ⋅ 531 mod 881
≡ 68760 ⋅ 394 ⋅ 800 ⋅ 41 ⋅ 531 mod 881 ≡ 42 ⋅ 394 ⋅ 800 ⋅ 41 ⋅ 531 mod 881
≡ 16548 ⋅ 800 ⋅ 41 ⋅ 531 mod 881 ≡ 690 ⋅ 800 ⋅ 41 ⋅ 531 mod 881
≡ 552000 ⋅ 41 ⋅ 531 mod 881 ≡ 494 ⋅ 41 ⋅ 531 mod 881
≡ 20254 ⋅ 531 mod 881 ≡ 872 ⋅ 531 mod 881
≡ 463032 mod 881 ≡ 507 mod 881

Es gilt also: 531²²³ ≡ 507 mod 881

Berechnung des größten gemeinsamen Teilers von 89 und 60

=>89	= 1⋅60 + 29
=>60	= 2⋅29 + 2
=>29	= 14⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(89,60)=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= 29-14⋅2
2= 60-2⋅29	eingesetzt in die Zeile drüber:	1	= 1⋅29 -14⋅(60 -2⋅ 29) = 1⋅29 -14⋅60 +28⋅ 29) = -14⋅60 +29⋅ 29 (=1)
29= 89-1⋅60	eingesetzt in die Zeile drüber:	1	= -14⋅60 +29⋅(89 -1⋅ 60) = -14⋅60 +29⋅89 -29⋅ 60) = 29⋅89 -43⋅ 60 (=1)

Es gilt also: ggt(89,60)=1 = 29⋅89 -43⋅60

oder wenn man 29⋅89 auf die linke Seite bringt:

1 -29⋅89 = -43⋅60

-43⋅60 = -29⋅89 + 1 |+89⋅60

-43⋅60 + 89⋅60 = -29⋅89 + 89⋅60 + 1

(-43 + 89) ⋅ 60 = (-29 + 60) ⋅ 89 + 1

46⋅60 = 31⋅89 + 1

Es gilt also: 46⋅60 = 31⋅89 +1

Somit 46⋅60 = 1 mod 89

46 ist also das Inverse von 60 mod 89