Um längere Rechnungen zu vermeiden, rechnen wir:

(1196 - 2399) mod 6 ≡ (1196 mod 6 - 2399 mod 6) mod 6.

1196 mod 6 ≡ 2 mod 6 kann man relativ leicht bestimmen, weil ja 1196 = 1200-4 = 6 ⋅ 200 -4 = 6 ⋅ 200 - 6 + 2.

2399 mod 6 ≡ 5 mod 6 kann man relativ leicht bestimmen, weil ja 2399 = 2400-1 = 6 ⋅ 400 -1 = 6 ⋅ 400 - 6 + 5.

Somit gilt:

(1196 - 2399) mod 6 ≡ (2 - 5) mod 6 ≡ -3 mod 6 ≡ 3 mod 6.

Um längere Rechnungen zu vermeiden, rechnen wir:

(70 ⋅ 26) mod 6 ≡ (70 mod 6 ⋅ 26 mod 6) mod 6.

70 mod 6 ≡ 4 mod 6 kann man relativ leicht bestimmen, weil ja 70 = 66 + 4 = 11 ⋅ 6 + 4 ist.

26 mod 6 ≡ 2 mod 6 kann man relativ leicht bestimmen, weil ja 26 = 24 + 2 = 4 ⋅ 6 + 2 ist.

Somit gilt:

(70 ⋅ 26) mod 6 ≡ (4 ⋅ 2) mod 6 ≡ 8 mod 6 ≡ 2 mod 6.

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

2: 342²=342¹⁺¹=342¹⋅342¹ ≡ 342⋅342=116964 ≡ 159 mod 599

4: 342⁴=342²⁺²=342²⋅342² ≡ 159⋅159=25281 ≡ 123 mod 599

8: 342⁸=342⁴⁺⁴=342⁴⋅342⁴ ≡ 123⋅123=15129 ≡ 154 mod 599

16: 342¹⁶=342⁸⁺⁸=342⁸⋅342⁸ ≡ 154⋅154=23716 ≡ 355 mod 599

32: 342³²=342¹⁶⁺¹⁶=342¹⁶⋅342¹⁶ ≡ 355⋅355=126025 ≡ 235 mod 599

64: 342⁶⁴=342³²⁺³²=342³²⋅342³² ≡ 235⋅235=55225 ≡ 117 mod 599

128: 342¹²⁸=342⁶⁴⁺⁶⁴=342⁶⁴⋅342⁶⁴ ≡ 117⋅117=13689 ≡ 511 mod 599

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

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

127 = 64+32+16+8+4+2+1

757¹²⁷

= 757^{64+32+16+8+4+2+1}

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

≡ 627 ⋅ 931 ⋅ 137 ⋅ 549 ⋅ 568 ⋅ 251 ⋅ 757 mod 991
≡ 583737 ⋅ 137 ⋅ 549 ⋅ 568 ⋅ 251 ⋅ 757 mod 991 ≡ 38 ⋅ 137 ⋅ 549 ⋅ 568 ⋅ 251 ⋅ 757 mod 991
≡ 5206 ⋅ 549 ⋅ 568 ⋅ 251 ⋅ 757 mod 991 ≡ 251 ⋅ 549 ⋅ 568 ⋅ 251 ⋅ 757 mod 991
≡ 137799 ⋅ 568 ⋅ 251 ⋅ 757 mod 991 ≡ 50 ⋅ 568 ⋅ 251 ⋅ 757 mod 991
≡ 28400 ⋅ 251 ⋅ 757 mod 991 ≡ 652 ⋅ 251 ⋅ 757 mod 991
≡ 163652 ⋅ 757 mod 991 ≡ 137 ⋅ 757 mod 991
≡ 103709 mod 991 ≡ 645 mod 991

Es gilt also: 757¹²⁷ ≡ 645 mod 991

Berechnung des größten gemeinsamen Teilers von 97 und 87

=>97	= 1⋅87 + 10
=>87	= 8⋅10 + 7
=>10	= 1⋅7 + 3
=>7	= 2⋅3 + 1
=>3	= 3⋅1 + 0

also gilt: ggt(97,87)=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= 7-2⋅3
3= 10-1⋅7	eingesetzt in die Zeile drüber:	1	= 1⋅7 -2⋅(10 -1⋅ 7) = 1⋅7 -2⋅10 +2⋅ 7) = -2⋅10 +3⋅ 7 (=1)
7= 87-8⋅10	eingesetzt in die Zeile drüber:	1	= -2⋅10 +3⋅(87 -8⋅ 10) = -2⋅10 +3⋅87 -24⋅ 10) = 3⋅87 -26⋅ 10 (=1)
10= 97-1⋅87	eingesetzt in die Zeile drüber:	1	= 3⋅87 -26⋅(97 -1⋅ 87) = 3⋅87 -26⋅97 +26⋅ 87) = -26⋅97 +29⋅ 87 (=1)

Es gilt also: ggt(97,87)=1 = -26⋅97 +29⋅87

oder wenn man -26⋅97 auf die linke Seite bringt:

1 +26⋅97 = +29⋅87

Es gilt also: 29⋅87 = 26⋅97 +1

Somit 29⋅87 = 1 mod 97

29 ist also das Inverse von 87 mod 97