Um längere Rechnungen zu vermeiden, rechnen wir:

(1199 + 124) mod 4 ≡ (1199 mod 4 + 124 mod 4) mod 4.

1199 mod 4 ≡ 3 mod 4 kann man relativ leicht bestimmen, weil ja 1199 = 1100+99 = 4 ⋅ 275 +99.

124 mod 4 ≡ 0 mod 4 kann man relativ leicht bestimmen, weil ja 124 = 120+4 = 4 ⋅ 30 +4.

Somit gilt:

(1199 + 124) mod 4 ≡ (3 + 0) mod 4 ≡ 3 mod 4.

Um längere Rechnungen zu vermeiden, rechnen wir:

(93 ⋅ 33) mod 5 ≡ (93 mod 5 ⋅ 33 mod 5) mod 5.

93 mod 5 ≡ 3 mod 5 kann man relativ leicht bestimmen, weil ja 93 = 90 + 3 = 18 ⋅ 5 + 3 ist.

33 mod 5 ≡ 3 mod 5 kann man relativ leicht bestimmen, weil ja 33 = 30 + 3 = 6 ⋅ 5 + 3 ist.

Somit gilt:

(93 ⋅ 33) mod 5 ≡ (3 ⋅ 3) mod 5 ≡ 9 mod 5 ≡ 4 mod 5.

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

2: 330²=330¹⁺¹=330¹⋅330¹ ≡ 330⋅330=108900 ≡ 423 mod 709

4: 330⁴=330²⁺²=330²⋅330² ≡ 423⋅423=178929 ≡ 261 mod 709

8: 330⁸=330⁴⁺⁴=330⁴⋅330⁴ ≡ 261⋅261=68121 ≡ 57 mod 709

16: 330¹⁶=330⁸⁺⁸=330⁸⋅330⁸ ≡ 57⋅57=3249 ≡ 413 mod 709

32: 330³²=330¹⁶⁺¹⁶=330¹⁶⋅330¹⁶ ≡ 413⋅413=170569 ≡ 409 mod 709

64: 330⁶⁴=330³²⁺³²=330³²⋅330³² ≡ 409⋅409=167281 ≡ 666 mod 709

128: 330¹²⁸=330⁶⁴⁺⁶⁴=330⁶⁴⋅330⁶⁴ ≡ 666⋅666=443556 ≡ 431 mod 709

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

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

239 = 128+64+32+8+4+2+1

199²³⁹

= 199^{128+64+32+8+4+2+1}

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

≡ 146 ⋅ 121 ⋅ 212 ⋅ 74 ⋅ 175 ⋅ 130 ⋅ 199 mod 223
≡ 17666 ⋅ 212 ⋅ 74 ⋅ 175 ⋅ 130 ⋅ 199 mod 223 ≡ 49 ⋅ 212 ⋅ 74 ⋅ 175 ⋅ 130 ⋅ 199 mod 223
≡ 10388 ⋅ 74 ⋅ 175 ⋅ 130 ⋅ 199 mod 223 ≡ 130 ⋅ 74 ⋅ 175 ⋅ 130 ⋅ 199 mod 223
≡ 9620 ⋅ 175 ⋅ 130 ⋅ 199 mod 223 ≡ 31 ⋅ 175 ⋅ 130 ⋅ 199 mod 223
≡ 5425 ⋅ 130 ⋅ 199 mod 223 ≡ 73 ⋅ 130 ⋅ 199 mod 223
≡ 9490 ⋅ 199 mod 223 ≡ 124 ⋅ 199 mod 223
≡ 24676 mod 223 ≡ 146 mod 223

Es gilt also: 199²³⁹ ≡ 146 mod 223

Berechnung des größten gemeinsamen Teilers von 79 und 32

=>79	= 2⋅32 + 15
=>32	= 2⋅15 + 2
=>15	= 7⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(79,32)=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= 15-7⋅2
2= 32-2⋅15	eingesetzt in die Zeile drüber:	1	= 1⋅15 -7⋅(32 -2⋅ 15) = 1⋅15 -7⋅32 +14⋅ 15) = -7⋅32 +15⋅ 15 (=1)
15= 79-2⋅32	eingesetzt in die Zeile drüber:	1	= -7⋅32 +15⋅(79 -2⋅ 32) = -7⋅32 +15⋅79 -30⋅ 32) = 15⋅79 -37⋅ 32 (=1)

Es gilt also: ggt(79,32)=1 = 15⋅79 -37⋅32

oder wenn man 15⋅79 auf die linke Seite bringt:

1 -15⋅79 = -37⋅32

-37⋅32 = -15⋅79 + 1 |+79⋅32

-37⋅32 + 79⋅32 = -15⋅79 + 79⋅32 + 1

(-37 + 79) ⋅ 32 = (-15 + 32) ⋅ 79 + 1

42⋅32 = 17⋅79 + 1

Es gilt also: 42⋅32 = 17⋅79 +1

Somit 42⋅32 = 1 mod 79

42 ist also das Inverse von 32 mod 79