Um längere Rechnungen zu vermeiden, rechnen wir:

(17996 + 599) mod 6 ≡ (17996 mod 6 + 599 mod 6) mod 6.

17996 mod 6 ≡ 2 mod 6 kann man relativ leicht bestimmen, weil ja 17996 = 18000-4 = 6 ⋅ 3000 -4 = 6 ⋅ 3000 - 6 + 2.

599 mod 6 ≡ 5 mod 6 kann man relativ leicht bestimmen, weil ja 599 = 600-1 = 6 ⋅ 100 -1 = 6 ⋅ 100 - 6 + 5.

Somit gilt:

(17996 + 599) mod 6 ≡ (2 + 5) mod 6 ≡ 7 mod 6 ≡ 1 mod 6.

Um längere Rechnungen zu vermeiden, rechnen wir:

(36 ⋅ 55) mod 7 ≡ (36 mod 7 ⋅ 55 mod 7) mod 7.

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

55 mod 7 ≡ 6 mod 7 kann man relativ leicht bestimmen, weil ja 55 = 49 + 6 = 7 ⋅ 7 + 6 ist.

Somit gilt:

(36 ⋅ 55) mod 7 ≡ (1 ⋅ 6) mod 7 ≡ 6 mod 7.

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

2: 784²=784¹⁺¹=784¹⋅784¹ ≡ 784⋅784=614656 ≡ 183 mod 941

4: 784⁴=784²⁺²=784²⋅784² ≡ 183⋅183=33489 ≡ 554 mod 941

8: 784⁸=784⁴⁺⁴=784⁴⋅784⁴ ≡ 554⋅554=306916 ≡ 150 mod 941

16: 784¹⁶=784⁸⁺⁸=784⁸⋅784⁸ ≡ 150⋅150=22500 ≡ 857 mod 941

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

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

182 = 128+32+16+4+2

688¹⁸²

= 688^{128+32+16+4+2}

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

≡ 143 ⋅ 684 ⋅ 508 ⋅ 270 ⋅ 219 mod 757
≡ 97812 ⋅ 508 ⋅ 270 ⋅ 219 mod 757 ≡ 159 ⋅ 508 ⋅ 270 ⋅ 219 mod 757
≡ 80772 ⋅ 270 ⋅ 219 mod 757 ≡ 530 ⋅ 270 ⋅ 219 mod 757
≡ 143100 ⋅ 219 mod 757 ≡ 27 ⋅ 219 mod 757
≡ 5913 mod 757 ≡ 614 mod 757

Es gilt also: 688¹⁸² ≡ 614 mod 757

Berechnung des größten gemeinsamen Teilers von 61 und 23

=>61	= 2⋅23 + 15
=>23	= 1⋅15 + 8
=>15	= 1⋅8 + 7
=>8	= 1⋅7 + 1
=>7	= 7⋅1 + 0

also gilt: ggt(61,23)=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= 8-1⋅7
7= 15-1⋅8	eingesetzt in die Zeile drüber:	1	= 1⋅8 -1⋅(15 -1⋅ 8) = 1⋅8 -1⋅15 +1⋅ 8) = -1⋅15 +2⋅ 8 (=1)
8= 23-1⋅15	eingesetzt in die Zeile drüber:	1	= -1⋅15 +2⋅(23 -1⋅ 15) = -1⋅15 +2⋅23 -2⋅ 15) = 2⋅23 -3⋅ 15 (=1)
15= 61-2⋅23	eingesetzt in die Zeile drüber:	1	= 2⋅23 -3⋅(61 -2⋅ 23) = 2⋅23 -3⋅61 +6⋅ 23) = -3⋅61 +8⋅ 23 (=1)

Es gilt also: ggt(61,23)=1 = -3⋅61 +8⋅23

oder wenn man -3⋅61 auf die linke Seite bringt:

1 +3⋅61 = +8⋅23

Es gilt also: 8⋅23 = 3⋅61 +1

Somit 8⋅23 = 1 mod 61

8 ist also das Inverse von 23 mod 61