Um längere Rechnungen zu vermeiden, rechnen wir:

(29994 - 181) mod 6 ≡ (29994 mod 6 - 181 mod 6) mod 6.

29994 mod 6 ≡ 0 mod 6 kann man relativ leicht bestimmen, weil ja 29994 = 30000-6 = 6 ⋅ 5000 -6 = 6 ⋅ 5000 - 6 + 0.

181 mod 6 ≡ 1 mod 6 kann man relativ leicht bestimmen, weil ja 181 = 180+1 = 6 ⋅ 30 +1.

Somit gilt:

(29994 - 181) mod 6 ≡ (0 - 1) mod 6 ≡ -1 mod 6 ≡ 5 mod 6.

Um längere Rechnungen zu vermeiden, rechnen wir:

(85 ⋅ 69) mod 5 ≡ (85 mod 5 ⋅ 69 mod 5) mod 5.

85 mod 5 ≡ 0 mod 5 kann man relativ leicht bestimmen, weil ja 85 = 85 + 0 = 17 ⋅ 5 + 0 ist.

69 mod 5 ≡ 4 mod 5 kann man relativ leicht bestimmen, weil ja 69 = 65 + 4 = 13 ⋅ 5 + 4 ist.

Somit gilt:

(85 ⋅ 69) mod 5 ≡ (0 ⋅ 4) mod 5 ≡ 0 mod 5.

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

2: 217²=217¹⁺¹=217¹⋅217¹ ≡ 217⋅217=47089 ≡ 261 mod 509

4: 217⁴=217²⁺²=217²⋅217² ≡ 261⋅261=68121 ≡ 424 mod 509

8: 217⁸=217⁴⁺⁴=217⁴⋅217⁴ ≡ 424⋅424=179776 ≡ 99 mod 509

16: 217¹⁶=217⁸⁺⁸=217⁸⋅217⁸ ≡ 99⋅99=9801 ≡ 130 mod 509

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

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

183 = 128+32+16+4+2+1

401¹⁸³

= 401^{128+32+16+4+2+1}

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

≡ 416 ⋅ 689 ⋅ 719 ⋅ 262 ⋅ 253 ⋅ 401 mod 787
≡ 286624 ⋅ 719 ⋅ 262 ⋅ 253 ⋅ 401 mod 787 ≡ 156 ⋅ 719 ⋅ 262 ⋅ 253 ⋅ 401 mod 787
≡ 112164 ⋅ 262 ⋅ 253 ⋅ 401 mod 787 ≡ 410 ⋅ 262 ⋅ 253 ⋅ 401 mod 787
≡ 107420 ⋅ 253 ⋅ 401 mod 787 ≡ 388 ⋅ 253 ⋅ 401 mod 787
≡ 98164 ⋅ 401 mod 787 ≡ 576 ⋅ 401 mod 787
≡ 230976 mod 787 ≡ 385 mod 787

Es gilt also: 401¹⁸³ ≡ 385 mod 787

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

=>71	= 2⋅33 + 5
=>33	= 6⋅5 + 3
=>5	= 1⋅3 + 2
=>3	= 1⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(71,33)=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= 3-1⋅2
2= 5-1⋅3	eingesetzt in die Zeile drüber:	1	= 1⋅3 -1⋅(5 -1⋅ 3) = 1⋅3 -1⋅5 +1⋅ 3) = -1⋅5 +2⋅ 3 (=1)
3= 33-6⋅5	eingesetzt in die Zeile drüber:	1	= -1⋅5 +2⋅(33 -6⋅ 5) = -1⋅5 +2⋅33 -12⋅ 5) = 2⋅33 -13⋅ 5 (=1)
5= 71-2⋅33	eingesetzt in die Zeile drüber:	1	= 2⋅33 -13⋅(71 -2⋅ 33) = 2⋅33 -13⋅71 +26⋅ 33) = -13⋅71 +28⋅ 33 (=1)

Es gilt also: ggt(71,33)=1 = -13⋅71 +28⋅33

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

1 +13⋅71 = +28⋅33

Es gilt also: 28⋅33 = 13⋅71 +1

Somit 28⋅33 = 1 mod 71

28 ist also das Inverse von 33 mod 71