Um längere Rechnungen zu vermeiden, rechnen wir:

(16000 + 4008) mod 8 ≡ (16000 mod 8 + 4008 mod 8) mod 8.

16000 mod 8 ≡ 0 mod 8 kann man relativ leicht bestimmen, weil ja 16000 = 16000+0 = 8 ⋅ 2000 +0.

4008 mod 8 ≡ 0 mod 8 kann man relativ leicht bestimmen, weil ja 4008 = 4000+8 = 8 ⋅ 500 +8.

Somit gilt:

(16000 + 4008) mod 8 ≡ (0 + 0) mod 8 ≡ 0 mod 8.

Um längere Rechnungen zu vermeiden, rechnen wir:

(58 ⋅ 76) mod 4 ≡ (58 mod 4 ⋅ 76 mod 4) mod 4.

58 mod 4 ≡ 2 mod 4 kann man relativ leicht bestimmen, weil ja 58 = 56 + 2 = 14 ⋅ 4 + 2 ist.

76 mod 4 ≡ 0 mod 4 kann man relativ leicht bestimmen, weil ja 76 = 76 + 0 = 19 ⋅ 4 + 0 ist.

Somit gilt:

(58 ⋅ 76) mod 4 ≡ (2 ⋅ 0) mod 4 ≡ 0 mod 4.

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

2: 760²=760¹⁺¹=760¹⋅760¹ ≡ 760⋅760=577600 ≡ 729 mod 787

4: 760⁴=760²⁺²=760²⋅760² ≡ 729⋅729=531441 ≡ 216 mod 787

8: 760⁸=760⁴⁺⁴=760⁴⋅760⁴ ≡ 216⋅216=46656 ≡ 223 mod 787

16: 760¹⁶=760⁸⁺⁸=760⁸⋅760⁸ ≡ 223⋅223=49729 ≡ 148 mod 787

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

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

246 = 128+64+32+16+4+2

438²⁴⁶

= 438^{128+64+32+16+4+2}

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

≡ 4 ⋅ 521 ⋅ 467 ⋅ 102 ⋅ 518 ⋅ 426 mod 523
≡ 2084 ⋅ 467 ⋅ 102 ⋅ 518 ⋅ 426 mod 523 ≡ 515 ⋅ 467 ⋅ 102 ⋅ 518 ⋅ 426 mod 523
≡ 240505 ⋅ 102 ⋅ 518 ⋅ 426 mod 523 ≡ 448 ⋅ 102 ⋅ 518 ⋅ 426 mod 523
≡ 45696 ⋅ 518 ⋅ 426 mod 523 ≡ 195 ⋅ 518 ⋅ 426 mod 523
≡ 101010 ⋅ 426 mod 523 ≡ 71 ⋅ 426 mod 523
≡ 30246 mod 523 ≡ 435 mod 523

Es gilt also: 438²⁴⁶ ≡ 435 mod 523

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

=>61	= 3⋅19 + 4
=>19	= 4⋅4 + 3
=>4	= 1⋅3 + 1
=>3	= 3⋅1 + 0

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

Es gilt also: ggt(61,19)=1 = 5⋅61 -16⋅19

oder wenn man 5⋅61 auf die linke Seite bringt:

1 -5⋅61 = -16⋅19

-16⋅19 = -5⋅61 + 1 |+61⋅19

-16⋅19 + 61⋅19 = -5⋅61 + 61⋅19 + 1

(-16 + 61) ⋅ 19 = (-5 + 19) ⋅ 61 + 1

45⋅19 = 14⋅61 + 1

Es gilt also: 45⋅19 = 14⋅61 +1

Somit 45⋅19 = 1 mod 61

45 ist also das Inverse von 19 mod 61