Um längere Rechnungen zu vermeiden, rechnen wir:

(74 - 3999) mod 8 ≡ (74 mod 8 - 3999 mod 8) mod 8.

74 mod 8 ≡ 2 mod 8 kann man relativ leicht bestimmen, weil ja 74 = 80-6 = 8 ⋅ 10 -6 = 8 ⋅ 10 - 8 + 2.

3999 mod 8 ≡ 7 mod 8 kann man relativ leicht bestimmen, weil ja 3999 = 4000-1 = 8 ⋅ 500 -1 = 8 ⋅ 500 - 8 + 7.

Somit gilt:

(74 - 3999) mod 8 ≡ (2 - 7) mod 8 ≡ -5 mod 8 ≡ 3 mod 8.

Um längere Rechnungen zu vermeiden, rechnen wir:

(43 ⋅ 55) mod 10 ≡ (43 mod 10 ⋅ 55 mod 10) mod 10.

43 mod 10 ≡ 3 mod 10 kann man relativ leicht bestimmen, weil ja 43 = 40 + 3 = 4 ⋅ 10 + 3 ist.

55 mod 10 ≡ 5 mod 10 kann man relativ leicht bestimmen, weil ja 55 = 50 + 5 = 5 ⋅ 10 + 5 ist.

Somit gilt:

(43 ⋅ 55) mod 10 ≡ (3 ⋅ 5) mod 10 ≡ 15 mod 10 ≡ 5 mod 10.

Die 32 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: 186¹=186

2: 186²=186¹⁺¹=186¹⋅186¹ ≡ 186⋅186=34596 ≡ 133 mod 241

4: 186⁴=186²⁺²=186²⋅186² ≡ 133⋅133=17689 ≡ 96 mod 241

8: 186⁸=186⁴⁺⁴=186⁴⋅186⁴ ≡ 96⋅96=9216 ≡ 58 mod 241

16: 186¹⁶=186⁸⁺⁸=186⁸⋅186⁸ ≡ 58⋅58=3364 ≡ 231 mod 241

32: 186³²=186¹⁶⁺¹⁶=186¹⁶⋅186¹⁶ ≡ 231⋅231=53361 ≡ 100 mod 241

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

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

191 = 128+32+16+8+4+2+1

269¹⁹¹

= 269^{128+32+16+8+4+2+1}

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

≡ 299 ⋅ 41 ⋅ 797 ⋅ 308 ⋅ 764 ⋅ 732 ⋅ 269 mod 863
≡ 12259 ⋅ 797 ⋅ 308 ⋅ 764 ⋅ 732 ⋅ 269 mod 863 ≡ 177 ⋅ 797 ⋅ 308 ⋅ 764 ⋅ 732 ⋅ 269 mod 863
≡ 141069 ⋅ 308 ⋅ 764 ⋅ 732 ⋅ 269 mod 863 ≡ 400 ⋅ 308 ⋅ 764 ⋅ 732 ⋅ 269 mod 863
≡ 123200 ⋅ 764 ⋅ 732 ⋅ 269 mod 863 ≡ 654 ⋅ 764 ⋅ 732 ⋅ 269 mod 863
≡ 499656 ⋅ 732 ⋅ 269 mod 863 ≡ 842 ⋅ 732 ⋅ 269 mod 863
≡ 616344 ⋅ 269 mod 863 ≡ 162 ⋅ 269 mod 863
≡ 43578 mod 863 ≡ 428 mod 863

Es gilt also: 269¹⁹¹ ≡ 428 mod 863

Berechnung des größten gemeinsamen Teilers von 53 und 44

=>53	= 1⋅44 + 9
=>44	= 4⋅9 + 8
=>9	= 1⋅8 + 1
=>8	= 8⋅1 + 0

also gilt: ggt(53,44)=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= 9-1⋅8
8= 44-4⋅9	eingesetzt in die Zeile drüber:	1	= 1⋅9 -1⋅(44 -4⋅ 9) = 1⋅9 -1⋅44 +4⋅ 9) = -1⋅44 +5⋅ 9 (=1)
9= 53-1⋅44	eingesetzt in die Zeile drüber:	1	= -1⋅44 +5⋅(53 -1⋅ 44) = -1⋅44 +5⋅53 -5⋅ 44) = 5⋅53 -6⋅ 44 (=1)

Es gilt also: ggt(53,44)=1 = 5⋅53 -6⋅44

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

1 -5⋅53 = -6⋅44

-6⋅44 = -5⋅53 + 1 |+53⋅44

-6⋅44 + 53⋅44 = -5⋅53 + 53⋅44 + 1

(-6 + 53) ⋅ 44 = (-5 + 44) ⋅ 53 + 1

47⋅44 = 39⋅53 + 1

Es gilt also: 47⋅44 = 39⋅53 +1

Somit 47⋅44 = 1 mod 53

47 ist also das Inverse von 44 mod 53