Um längere Rechnungen zu vermeiden, rechnen wir:

(14999 + 1998) mod 5 ≡ (14999 mod 5 + 1998 mod 5) mod 5.

14999 mod 5 ≡ 4 mod 5 kann man relativ leicht bestimmen, weil ja 14999 = 14000+999 = 5 ⋅ 2800 +999.

1998 mod 5 ≡ 3 mod 5 kann man relativ leicht bestimmen, weil ja 1998 = 1900+98 = 5 ⋅ 380 +98.

Somit gilt:

(14999 + 1998) mod 5 ≡ (4 + 3) mod 5 ≡ 7 mod 5 ≡ 2 mod 5.

Um längere Rechnungen zu vermeiden, rechnen wir:

(21 ⋅ 22) mod 8 ≡ (21 mod 8 ⋅ 22 mod 8) mod 8.

21 mod 8 ≡ 5 mod 8 kann man relativ leicht bestimmen, weil ja 21 = 16 + 5 = 2 ⋅ 8 + 5 ist.

22 mod 8 ≡ 6 mod 8 kann man relativ leicht bestimmen, weil ja 22 = 16 + 6 = 2 ⋅ 8 + 6 ist.

Somit gilt:

(21 ⋅ 22) mod 8 ≡ (5 ⋅ 6) mod 8 ≡ 30 mod 8 ≡ 6 mod 8.

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

2: 267²=267¹⁺¹=267¹⋅267¹ ≡ 267⋅267=71289 ≡ 93 mod 349

4: 267⁴=267²⁺²=267²⋅267² ≡ 93⋅93=8649 ≡ 273 mod 349

8: 267⁸=267⁴⁺⁴=267⁴⋅267⁴ ≡ 273⋅273=74529 ≡ 192 mod 349

16: 267¹⁶=267⁸⁺⁸=267⁸⋅267⁸ ≡ 192⋅192=36864 ≡ 219 mod 349

32: 267³²=267¹⁶⁺¹⁶=267¹⁶⋅267¹⁶ ≡ 219⋅219=47961 ≡ 148 mod 349

64: 267⁶⁴=267³²⁺³²=267³²⋅267³² ≡ 148⋅148=21904 ≡ 266 mod 349

128: 267¹²⁸=267⁶⁴⁺⁶⁴=267⁶⁴⋅267⁶⁴ ≡ 266⋅266=70756 ≡ 258 mod 349

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

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

235 = 128+64+32+8+2+1

584²³⁵

= 584^{128+64+32+8+2+1}

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

≡ 361 ⋅ 19 ⋅ 824 ⋅ 220 ⋅ 82 ⋅ 584 mod 997
≡ 6859 ⋅ 824 ⋅ 220 ⋅ 82 ⋅ 584 mod 997 ≡ 877 ⋅ 824 ⋅ 220 ⋅ 82 ⋅ 584 mod 997
≡ 722648 ⋅ 220 ⋅ 82 ⋅ 584 mod 997 ≡ 820 ⋅ 220 ⋅ 82 ⋅ 584 mod 997
≡ 180400 ⋅ 82 ⋅ 584 mod 997 ≡ 940 ⋅ 82 ⋅ 584 mod 997
≡ 77080 ⋅ 584 mod 997 ≡ 311 ⋅ 584 mod 997
≡ 181624 mod 997 ≡ 170 mod 997

Es gilt also: 584²³⁵ ≡ 170 mod 997

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

=>83	= 1⋅55 + 28
=>55	= 1⋅28 + 27
=>28	= 1⋅27 + 1
=>27	= 27⋅1 + 0

also gilt: ggt(83,55)=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= 28-1⋅27
27= 55-1⋅28	eingesetzt in die Zeile drüber:	1	= 1⋅28 -1⋅(55 -1⋅ 28) = 1⋅28 -1⋅55 +1⋅ 28) = -1⋅55 +2⋅ 28 (=1)
28= 83-1⋅55	eingesetzt in die Zeile drüber:	1	= -1⋅55 +2⋅(83 -1⋅ 55) = -1⋅55 +2⋅83 -2⋅ 55) = 2⋅83 -3⋅ 55 (=1)

Es gilt also: ggt(83,55)=1 = 2⋅83 -3⋅55

oder wenn man 2⋅83 auf die linke Seite bringt:

1 -2⋅83 = -3⋅55

-3⋅55 = -2⋅83 + 1 |+83⋅55

-3⋅55 + 83⋅55 = -2⋅83 + 83⋅55 + 1

(-3 + 83) ⋅ 55 = (-2 + 55) ⋅ 83 + 1

80⋅55 = 53⋅83 + 1

Es gilt also: 80⋅55 = 53⋅83 +1

Somit 80⋅55 = 1 mod 83

80 ist also das Inverse von 55 mod 83