Um längere Rechnungen zu vermeiden, rechnen wir:

(5997 - 12000) mod 3 ≡ (5997 mod 3 - 12000 mod 3) mod 3.

5997 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 5997 = 6000-3 = 3 ⋅ 2000 -3 = 3 ⋅ 2000 - 3 + 0.

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

Somit gilt:

(5997 - 12000) mod 3 ≡ (0 - 0) mod 3 ≡ 0 mod 3.

Um längere Rechnungen zu vermeiden, rechnen wir:

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

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

51 mod 4 ≡ 3 mod 4 kann man relativ leicht bestimmen, weil ja 51 = 48 + 3 = 12 ⋅ 4 + 3 ist.

Somit gilt:

(58 ⋅ 51) mod 4 ≡ (2 ⋅ 3) mod 4 ≡ 6 mod 4 ≡ 2 mod 4.

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

2: 293²=293¹⁺¹=293¹⋅293¹ ≡ 293⋅293=85849 ≡ 13 mod 311

4: 293⁴=293²⁺²=293²⋅293² ≡ 13⋅13=169 ≡ 169 mod 311

8: 293⁸=293⁴⁺⁴=293⁴⋅293⁴ ≡ 169⋅169=28561 ≡ 260 mod 311

16: 293¹⁶=293⁸⁺⁸=293⁸⋅293⁸ ≡ 260⋅260=67600 ≡ 113 mod 311

32: 293³²=293¹⁶⁺¹⁶=293¹⁶⋅293¹⁶ ≡ 113⋅113=12769 ≡ 18 mod 311

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

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

175 = 128+32+8+4+2+1

771¹⁷⁵

= 771^{128+32+8+4+2+1}

= 771¹²⁸⋅771³²⋅771⁸⋅771⁴⋅771²⋅771¹

≡ 809 ⋅ 579 ⋅ 358 ⋅ 506 ⋅ 832 ⋅ 771 mod 991
≡ 468411 ⋅ 358 ⋅ 506 ⋅ 832 ⋅ 771 mod 991 ≡ 659 ⋅ 358 ⋅ 506 ⋅ 832 ⋅ 771 mod 991
≡ 235922 ⋅ 506 ⋅ 832 ⋅ 771 mod 991 ≡ 64 ⋅ 506 ⋅ 832 ⋅ 771 mod 991
≡ 32384 ⋅ 832 ⋅ 771 mod 991 ≡ 672 ⋅ 832 ⋅ 771 mod 991
≡ 559104 ⋅ 771 mod 991 ≡ 180 ⋅ 771 mod 991
≡ 138780 mod 991 ≡ 40 mod 991

Es gilt also: 771¹⁷⁵ ≡ 40 mod 991

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

=>89	= 1⋅80 + 9
=>80	= 8⋅9 + 8
=>9	= 1⋅8 + 1
=>8	= 8⋅1 + 0

also gilt: ggt(89,80)=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= 80-8⋅9	eingesetzt in die Zeile drüber:	1	= 1⋅9 -1⋅(80 -8⋅ 9) = 1⋅9 -1⋅80 +8⋅ 9) = -1⋅80 +9⋅ 9 (=1)
9= 89-1⋅80	eingesetzt in die Zeile drüber:	1	= -1⋅80 +9⋅(89 -1⋅ 80) = -1⋅80 +9⋅89 -9⋅ 80) = 9⋅89 -10⋅ 80 (=1)

Es gilt also: ggt(89,80)=1 = 9⋅89 -10⋅80

oder wenn man 9⋅89 auf die linke Seite bringt:

1 -9⋅89 = -10⋅80

-10⋅80 = -9⋅89 + 1 |+89⋅80

-10⋅80 + 89⋅80 = -9⋅89 + 89⋅80 + 1

(-10 + 89) ⋅ 80 = (-9 + 80) ⋅ 89 + 1

79⋅80 = 71⋅89 + 1

Es gilt also: 79⋅80 = 71⋅89 +1

Somit 79⋅80 = 1 mod 89

79 ist also das Inverse von 80 mod 89