Um längere Rechnungen zu vermeiden, rechnen wir:

(7999 + 15999) mod 4 ≡ (7999 mod 4 + 15999 mod 4) mod 4.

7999 mod 4 ≡ 3 mod 4 kann man relativ leicht bestimmen, weil ja 7999 = 7000+999 = 4 ⋅ 1750 +999.

15999 mod 4 ≡ 3 mod 4 kann man relativ leicht bestimmen, weil ja 15999 = 15000+999 = 4 ⋅ 3750 +999.

Somit gilt:

(7999 + 15999) mod 4 ≡ (3 + 3) mod 4 ≡ 6 mod 4 ≡ 2 mod 4.

Um längere Rechnungen zu vermeiden, rechnen wir:

(91 ⋅ 87) mod 4 ≡ (91 mod 4 ⋅ 87 mod 4) mod 4.

91 mod 4 ≡ 3 mod 4 kann man relativ leicht bestimmen, weil ja 91 = 88 + 3 = 22 ⋅ 4 + 3 ist.

87 mod 4 ≡ 3 mod 4 kann man relativ leicht bestimmen, weil ja 87 = 84 + 3 = 21 ⋅ 4 + 3 ist.

Somit gilt:

(91 ⋅ 87) mod 4 ≡ (3 ⋅ 3) mod 4 ≡ 9 mod 4 ≡ 1 mod 4.

Die 128 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: 321¹=321

2: 321²=321¹⁺¹=321¹⋅321¹ ≡ 321⋅321=103041 ≡ 335 mod 577

4: 321⁴=321²⁺²=321²⋅321² ≡ 335⋅335=112225 ≡ 287 mod 577

8: 321⁸=321⁴⁺⁴=321⁴⋅321⁴ ≡ 287⋅287=82369 ≡ 435 mod 577

16: 321¹⁶=321⁸⁺⁸=321⁸⋅321⁸ ≡ 435⋅435=189225 ≡ 546 mod 577

32: 321³²=321¹⁶⁺¹⁶=321¹⁶⋅321¹⁶ ≡ 546⋅546=298116 ≡ 384 mod 577

64: 321⁶⁴=321³²⁺³²=321³²⋅321³² ≡ 384⋅384=147456 ≡ 321 mod 577

128: 321¹²⁸=321⁶⁴⁺⁶⁴=321⁶⁴⋅321⁶⁴ ≡ 321⋅321=103041 ≡ 335 mod 577

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

192¹⁸³

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

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

≡ 363 ⋅ 70 ⋅ 93 ⋅ 239 ⋅ 310 ⋅ 192 mod 373
≡ 25410 ⋅ 93 ⋅ 239 ⋅ 310 ⋅ 192 mod 373 ≡ 46 ⋅ 93 ⋅ 239 ⋅ 310 ⋅ 192 mod 373
≡ 4278 ⋅ 239 ⋅ 310 ⋅ 192 mod 373 ≡ 175 ⋅ 239 ⋅ 310 ⋅ 192 mod 373
≡ 41825 ⋅ 310 ⋅ 192 mod 373 ≡ 49 ⋅ 310 ⋅ 192 mod 373
≡ 15190 ⋅ 192 mod 373 ≡ 270 ⋅ 192 mod 373
≡ 51840 mod 373 ≡ 366 mod 373

Es gilt also: 192¹⁸³ ≡ 366 mod 373

Berechnung des größten gemeinsamen Teilers von 73 und 59

=>73	= 1⋅59 + 14
=>59	= 4⋅14 + 3
=>14	= 4⋅3 + 2
=>3	= 1⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(73,59)=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= 14-4⋅3	eingesetzt in die Zeile drüber:	1	= 1⋅3 -1⋅(14 -4⋅ 3) = 1⋅3 -1⋅14 +4⋅ 3) = -1⋅14 +5⋅ 3 (=1)
3= 59-4⋅14	eingesetzt in die Zeile drüber:	1	= -1⋅14 +5⋅(59 -4⋅ 14) = -1⋅14 +5⋅59 -20⋅ 14) = 5⋅59 -21⋅ 14 (=1)
14= 73-1⋅59	eingesetzt in die Zeile drüber:	1	= 5⋅59 -21⋅(73 -1⋅ 59) = 5⋅59 -21⋅73 +21⋅ 59) = -21⋅73 +26⋅ 59 (=1)

Es gilt also: ggt(73,59)=1 = -21⋅73 +26⋅59

oder wenn man -21⋅73 auf die linke Seite bringt:

1 +21⋅73 = +26⋅59

Es gilt also: 26⋅59 = 21⋅73 +1

Somit 26⋅59 = 1 mod 73

26 ist also das Inverse von 59 mod 73