Um längere Rechnungen zu vermeiden, rechnen wir:

(1199 - 598) mod 3 ≡ (1199 mod 3 - 598 mod 3) mod 3.

1199 mod 3 ≡ 2 mod 3 kann man relativ leicht bestimmen, weil ja 1199 = 1200-1 = 3 ⋅ 400 -1 = 3 ⋅ 400 - 3 + 2.

598 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 598 = 600-2 = 3 ⋅ 200 -2 = 3 ⋅ 200 - 3 + 1.

Somit gilt:

(1199 - 598) mod 3 ≡ (2 - 1) mod 3 ≡ 1 mod 3.

Um längere Rechnungen zu vermeiden, rechnen wir:

(40 ⋅ 30) mod 7 ≡ (40 mod 7 ⋅ 30 mod 7) mod 7.

40 mod 7 ≡ 5 mod 7 kann man relativ leicht bestimmen, weil ja 40 = 35 + 5 = 5 ⋅ 7 + 5 ist.

30 mod 7 ≡ 2 mod 7 kann man relativ leicht bestimmen, weil ja 30 = 28 + 2 = 4 ⋅ 7 + 2 ist.

Somit gilt:

(40 ⋅ 30) mod 7 ≡ (5 ⋅ 2) mod 7 ≡ 10 mod 7 ≡ 3 mod 7.

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

2: 396²=396¹⁺¹=396¹⋅396¹ ≡ 396⋅396=156816 ≡ 287 mod 997

4: 396⁴=396²⁺²=396²⋅396² ≡ 287⋅287=82369 ≡ 615 mod 997

8: 396⁸=396⁴⁺⁴=396⁴⋅396⁴ ≡ 615⋅615=378225 ≡ 362 mod 997

16: 396¹⁶=396⁸⁺⁸=396⁸⋅396⁸ ≡ 362⋅362=131044 ≡ 437 mod 997

32: 396³²=396¹⁶⁺¹⁶=396¹⁶⋅396¹⁶ ≡ 437⋅437=190969 ≡ 542 mod 997

64: 396⁶⁴=396³²⁺³²=396³²⋅396³² ≡ 542⋅542=293764 ≡ 646 mod 997

128: 396¹²⁸=396⁶⁴⁺⁶⁴=396⁶⁴⋅396⁶⁴ ≡ 646⋅646=417316 ≡ 570 mod 997

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

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

123 = 64+32+16+8+2+1

297¹²³

= 297^{64+32+16+8+2+1}

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

≡ 26 ⋅ 310 ⋅ 195 ⋅ 122 ⋅ 75 ⋅ 297 mod 397
≡ 8060 ⋅ 195 ⋅ 122 ⋅ 75 ⋅ 297 mod 397 ≡ 120 ⋅ 195 ⋅ 122 ⋅ 75 ⋅ 297 mod 397
≡ 23400 ⋅ 122 ⋅ 75 ⋅ 297 mod 397 ≡ 374 ⋅ 122 ⋅ 75 ⋅ 297 mod 397
≡ 45628 ⋅ 75 ⋅ 297 mod 397 ≡ 370 ⋅ 75 ⋅ 297 mod 397
≡ 27750 ⋅ 297 mod 397 ≡ 357 ⋅ 297 mod 397
≡ 106029 mod 397 ≡ 30 mod 397

Es gilt also: 297¹²³ ≡ 30 mod 397

Berechnung des größten gemeinsamen Teilers von 83 und 36

=>83	= 2⋅36 + 11
=>36	= 3⋅11 + 3
=>11	= 3⋅3 + 2
=>3	= 1⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(83,36)=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= 11-3⋅3	eingesetzt in die Zeile drüber:	1	= 1⋅3 -1⋅(11 -3⋅ 3) = 1⋅3 -1⋅11 +3⋅ 3) = -1⋅11 +4⋅ 3 (=1)
3= 36-3⋅11	eingesetzt in die Zeile drüber:	1	= -1⋅11 +4⋅(36 -3⋅ 11) = -1⋅11 +4⋅36 -12⋅ 11) = 4⋅36 -13⋅ 11 (=1)
11= 83-2⋅36	eingesetzt in die Zeile drüber:	1	= 4⋅36 -13⋅(83 -2⋅ 36) = 4⋅36 -13⋅83 +26⋅ 36) = -13⋅83 +30⋅ 36 (=1)

Es gilt also: ggt(83,36)=1 = -13⋅83 +30⋅36

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

1 +13⋅83 = +30⋅36

Es gilt also: 30⋅36 = 13⋅83 +1

Somit 30⋅36 = 1 mod 83

30 ist also das Inverse von 36 mod 83