Um längere Rechnungen zu vermeiden, rechnen wir:

(796 + 16000) mod 4 ≡ (796 mod 4 + 16000 mod 4) mod 4.

796 mod 4 ≡ 0 mod 4 kann man relativ leicht bestimmen, weil ja 796 = 700+96 = 4 ⋅ 175 +96.

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

Somit gilt:

(796 + 16000) mod 4 ≡ (0 + 0) mod 4 ≡ 0 mod 4.

Um längere Rechnungen zu vermeiden, rechnen wir:

(16 ⋅ 80) mod 4 ≡ (16 mod 4 ⋅ 80 mod 4) mod 4.

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

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

Somit gilt:

(16 ⋅ 80) mod 4 ≡ (0 ⋅ 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: 199¹=199

2: 199²=199¹⁺¹=199¹⋅199¹ ≡ 199⋅199=39601 ≡ 212 mod 331

4: 199⁴=199²⁺²=199²⋅199² ≡ 212⋅212=44944 ≡ 259 mod 331

8: 199⁸=199⁴⁺⁴=199⁴⋅199⁴ ≡ 259⋅259=67081 ≡ 219 mod 331

16: 199¹⁶=199⁸⁺⁸=199⁸⋅199⁸ ≡ 219⋅219=47961 ≡ 297 mod 331

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

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

63 = 32+16+8+4+2+1

478⁶³

= 478^{32+16+8+4+2+1}

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

≡ 225 ⋅ 15 ⋅ 200 ⋅ 270 ⋅ 206 ⋅ 478 mod 727
≡ 3375 ⋅ 200 ⋅ 270 ⋅ 206 ⋅ 478 mod 727 ≡ 467 ⋅ 200 ⋅ 270 ⋅ 206 ⋅ 478 mod 727
≡ 93400 ⋅ 270 ⋅ 206 ⋅ 478 mod 727 ≡ 344 ⋅ 270 ⋅ 206 ⋅ 478 mod 727
≡ 92880 ⋅ 206 ⋅ 478 mod 727 ≡ 551 ⋅ 206 ⋅ 478 mod 727
≡ 113506 ⋅ 478 mod 727 ≡ 94 ⋅ 478 mod 727
≡ 44932 mod 727 ≡ 585 mod 727

Es gilt also: 478⁶³ ≡ 585 mod 727

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

=>89	= 1⋅70 + 19
=>70	= 3⋅19 + 13
=>19	= 1⋅13 + 6
=>13	= 2⋅6 + 1
=>6	= 6⋅1 + 0

also gilt: ggt(89,70)=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= 13-2⋅6
6= 19-1⋅13	eingesetzt in die Zeile drüber:	1	= 1⋅13 -2⋅(19 -1⋅ 13) = 1⋅13 -2⋅19 +2⋅ 13) = -2⋅19 +3⋅ 13 (=1)
13= 70-3⋅19	eingesetzt in die Zeile drüber:	1	= -2⋅19 +3⋅(70 -3⋅ 19) = -2⋅19 +3⋅70 -9⋅ 19) = 3⋅70 -11⋅ 19 (=1)
19= 89-1⋅70	eingesetzt in die Zeile drüber:	1	= 3⋅70 -11⋅(89 -1⋅ 70) = 3⋅70 -11⋅89 +11⋅ 70) = -11⋅89 +14⋅ 70 (=1)

Es gilt also: ggt(89,70)=1 = -11⋅89 +14⋅70

oder wenn man -11⋅89 auf die linke Seite bringt:

1 +11⋅89 = +14⋅70

Es gilt also: 14⋅70 = 11⋅89 +1

Somit 14⋅70 = 1 mod 89

14 ist also das Inverse von 70 mod 89