Um längere Rechnungen zu vermeiden, rechnen wir:

(1196 + 119) mod 6 ≡ (1196 mod 6 + 119 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.

119 mod 6 ≡ 5 mod 6 kann man relativ leicht bestimmen, weil ja 119 = 120-1 = 6 ⋅ 20 -1 = 6 ⋅ 20 - 6 + 5.

Somit gilt:

(1196 + 119) mod 6 ≡ (2 + 5) mod 6 ≡ 7 mod 6 ≡ 1 mod 6.

Um längere Rechnungen zu vermeiden, rechnen wir:

(87 ⋅ 45) mod 8 ≡ (87 mod 8 ⋅ 45 mod 8) mod 8.

87 mod 8 ≡ 7 mod 8 kann man relativ leicht bestimmen, weil ja 87 = 80 + 7 = 10 ⋅ 8 + 7 ist.

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

Somit gilt:

(87 ⋅ 45) mod 8 ≡ (7 ⋅ 5) mod 8 ≡ 35 mod 8 ≡ 3 mod 8.

Die 16 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: 141¹=141

2: 141²=141¹⁺¹=141¹⋅141¹ ≡ 141⋅141=19881 ≡ 250 mod 293

4: 141⁴=141²⁺²=141²⋅141² ≡ 250⋅250=62500 ≡ 91 mod 293

8: 141⁸=141⁴⁺⁴=141⁴⋅141⁴ ≡ 91⋅91=8281 ≡ 77 mod 293

16: 141¹⁶=141⁸⁺⁸=141⁸⋅141⁸ ≡ 77⋅77=5929 ≡ 69 mod 293

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

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

213 = 128+64+16+4+1

783²¹³

= 783^{128+64+16+4+1}

= 783¹²⁸⋅783⁶⁴⋅783¹⁶⋅783⁴⋅783¹

≡ 790 ⋅ 436 ⋅ 605 ⋅ 700 ⋅ 783 mod 809
≡ 344440 ⋅ 605 ⋅ 700 ⋅ 783 mod 809 ≡ 615 ⋅ 605 ⋅ 700 ⋅ 783 mod 809
≡ 372075 ⋅ 700 ⋅ 783 mod 809 ≡ 744 ⋅ 700 ⋅ 783 mod 809
≡ 520800 ⋅ 783 mod 809 ≡ 613 ⋅ 783 mod 809
≡ 479979 mod 809 ≡ 242 mod 809

Es gilt also: 783²¹³ ≡ 242 mod 809

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

=>89	= 2⋅35 + 19
=>35	= 1⋅19 + 16
=>19	= 1⋅16 + 3
=>16	= 5⋅3 + 1
=>3	= 3⋅1 + 0

also gilt: ggt(89,35)=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= 16-5⋅3
3= 19-1⋅16	eingesetzt in die Zeile drüber:	1	= 1⋅16 -5⋅(19 -1⋅ 16) = 1⋅16 -5⋅19 +5⋅ 16) = -5⋅19 +6⋅ 16 (=1)
16= 35-1⋅19	eingesetzt in die Zeile drüber:	1	= -5⋅19 +6⋅(35 -1⋅ 19) = -5⋅19 +6⋅35 -6⋅ 19) = 6⋅35 -11⋅ 19 (=1)
19= 89-2⋅35	eingesetzt in die Zeile drüber:	1	= 6⋅35 -11⋅(89 -2⋅ 35) = 6⋅35 -11⋅89 +22⋅ 35) = -11⋅89 +28⋅ 35 (=1)

Es gilt also: ggt(89,35)=1 = -11⋅89 +28⋅35

oder wenn man -11⋅89 auf die linke Seite bringt:

1 +11⋅89 = +28⋅35

Es gilt also: 28⋅35 = 11⋅89 +1

Somit 28⋅35 = 1 mod 89

28 ist also das Inverse von 35 mod 89