Um längere Rechnungen zu vermeiden, rechnen wir:

(10001 - 496) mod 5 ≡ (10001 mod 5 - 496 mod 5) mod 5.

10001 mod 5 ≡ 1 mod 5 kann man relativ leicht bestimmen, weil ja 10001 = 10000+1 = 5 ⋅ 2000 +1.

496 mod 5 ≡ 1 mod 5 kann man relativ leicht bestimmen, weil ja 496 = 400+96 = 5 ⋅ 80 +96.

Somit gilt:

(10001 - 496) mod 5 ≡ (1 - 1) mod 5 ≡ 0 mod 5.

Um längere Rechnungen zu vermeiden, rechnen wir:

(81 ⋅ 22) mod 11 ≡ (81 mod 11 ⋅ 22 mod 11) mod 11.

81 mod 11 ≡ 4 mod 11 kann man relativ leicht bestimmen, weil ja 81 = 77 + 4 = 7 ⋅ 11 + 4 ist.

22 mod 11 ≡ 0 mod 11 kann man relativ leicht bestimmen, weil ja 22 = 22 + 0 = 2 ⋅ 11 + 0 ist.

Somit gilt:

(81 ⋅ 22) mod 11 ≡ (4 ⋅ 0) mod 11 ≡ 0 mod 11.

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

2: 331²=331¹⁺¹=331¹⋅331¹ ≡ 331⋅331=109561 ≡ 468 mod 859

4: 331⁴=331²⁺²=331²⋅331² ≡ 468⋅468=219024 ≡ 838 mod 859

8: 331⁸=331⁴⁺⁴=331⁴⋅331⁴ ≡ 838⋅838=702244 ≡ 441 mod 859

16: 331¹⁶=331⁸⁺⁸=331⁸⋅331⁸ ≡ 441⋅441=194481 ≡ 347 mod 859

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

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

217 = 128+64+16+8+1

498²¹⁷

= 498^{128+64+16+8+1}

= 498¹²⁸⋅498⁶⁴⋅498¹⁶⋅498⁸⋅498¹

≡ 328 ⋅ 49 ⋅ 484 ⋅ 22 ⋅ 498 mod 691
≡ 16072 ⋅ 484 ⋅ 22 ⋅ 498 mod 691 ≡ 179 ⋅ 484 ⋅ 22 ⋅ 498 mod 691
≡ 86636 ⋅ 22 ⋅ 498 mod 691 ≡ 261 ⋅ 22 ⋅ 498 mod 691
≡ 5742 ⋅ 498 mod 691 ≡ 214 ⋅ 498 mod 691
≡ 106572 mod 691 ≡ 158 mod 691

Es gilt also: 498²¹⁷ ≡ 158 mod 691

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

=>83	= 1⋅50 + 33
=>50	= 1⋅33 + 17
=>33	= 1⋅17 + 16
=>17	= 1⋅16 + 1
=>16	= 16⋅1 + 0

also gilt: ggt(83,50)=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= 17-1⋅16
16= 33-1⋅17	eingesetzt in die Zeile drüber:	1	= 1⋅17 -1⋅(33 -1⋅ 17) = 1⋅17 -1⋅33 +1⋅ 17) = -1⋅33 +2⋅ 17 (=1)
17= 50-1⋅33	eingesetzt in die Zeile drüber:	1	= -1⋅33 +2⋅(50 -1⋅ 33) = -1⋅33 +2⋅50 -2⋅ 33) = 2⋅50 -3⋅ 33 (=1)
33= 83-1⋅50	eingesetzt in die Zeile drüber:	1	= 2⋅50 -3⋅(83 -1⋅ 50) = 2⋅50 -3⋅83 +3⋅ 50) = -3⋅83 +5⋅ 50 (=1)

Es gilt also: ggt(83,50)=1 = -3⋅83 +5⋅50

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

1 +3⋅83 = +5⋅50

Es gilt also: 5⋅50 = 3⋅83 +1

Somit 5⋅50 = 1 mod 83

5 ist also das Inverse von 50 mod 83