Um längere Rechnungen zu vermeiden, rechnen wir:

(1999 + 16003) mod 4 ≡ (1999 mod 4 + 16003 mod 4) mod 4.

1999 mod 4 ≡ 3 mod 4 kann man relativ leicht bestimmen, weil ja 1999 = 1900+99 = 4 ⋅ 475 +99.

16003 mod 4 ≡ 3 mod 4 kann man relativ leicht bestimmen, weil ja 16003 = 16000+3 = 4 ⋅ 4000 +3.

Somit gilt:

(1999 + 16003) mod 4 ≡ (3 + 3) mod 4 ≡ 6 mod 4 ≡ 2 mod 4.

Um längere Rechnungen zu vermeiden, rechnen wir:

(65 ⋅ 83) mod 9 ≡ (65 mod 9 ⋅ 83 mod 9) mod 9.

65 mod 9 ≡ 2 mod 9 kann man relativ leicht bestimmen, weil ja 65 = 63 + 2 = 7 ⋅ 9 + 2 ist.

83 mod 9 ≡ 2 mod 9 kann man relativ leicht bestimmen, weil ja 83 = 81 + 2 = 9 ⋅ 9 + 2 ist.

Somit gilt:

(65 ⋅ 83) mod 9 ≡ (2 ⋅ 2) mod 9 ≡ 4 mod 9.

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

2: 238²=238¹⁺¹=238¹⋅238¹ ≡ 238⋅238=56644 ≡ 44 mod 283

4: 238⁴=238²⁺²=238²⋅238² ≡ 44⋅44=1936 ≡ 238 mod 283

8: 238⁸=238⁴⁺⁴=238⁴⋅238⁴ ≡ 238⋅238=56644 ≡ 44 mod 283

16: 238¹⁶=238⁸⁺⁸=238⁸⋅238⁸ ≡ 44⋅44=1936 ≡ 238 mod 283

32: 238³²=238¹⁶⁺¹⁶=238¹⁶⋅238¹⁶ ≡ 238⋅238=56644 ≡ 44 mod 283

64: 238⁶⁴=238³²⁺³²=238³²⋅238³² ≡ 44⋅44=1936 ≡ 238 mod 283

128: 238¹²⁸=238⁶⁴⁺⁶⁴=238⁶⁴⋅238⁶⁴ ≡ 238⋅238=56644 ≡ 44 mod 283

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

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

101 = 64+32+4+1

420¹⁰¹

= 420^64+32+4+1

= 420⁶⁴⋅420³²⋅420⁴⋅420¹

≡ 28 ⋅ 741 ⋅ 351 ⋅ 420 mod 887
≡ 20748 ⋅ 351 ⋅ 420 mod 887 ≡ 347 ⋅ 351 ⋅ 420 mod 887
≡ 121797 ⋅ 420 mod 887 ≡ 278 ⋅ 420 mod 887
≡ 116760 mod 887 ≡ 563 mod 887

Es gilt also: 420¹⁰¹ ≡ 563 mod 887

Berechnung des größten gemeinsamen Teilers von 71 und 48

=>71	= 1⋅48 + 23
=>48	= 2⋅23 + 2
=>23	= 11⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(71,48)=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= 23-11⋅2
2= 48-2⋅23	eingesetzt in die Zeile drüber:	1	= 1⋅23 -11⋅(48 -2⋅ 23) = 1⋅23 -11⋅48 +22⋅ 23) = -11⋅48 +23⋅ 23 (=1)
23= 71-1⋅48	eingesetzt in die Zeile drüber:	1	= -11⋅48 +23⋅(71 -1⋅ 48) = -11⋅48 +23⋅71 -23⋅ 48) = 23⋅71 -34⋅ 48 (=1)

Es gilt also: ggt(71,48)=1 = 23⋅71 -34⋅48

oder wenn man 23⋅71 auf die linke Seite bringt:

1 -23⋅71 = -34⋅48

-34⋅48 = -23⋅71 + 1 |+71⋅48

-34⋅48 + 71⋅48 = -23⋅71 + 71⋅48 + 1

(-34 + 71) ⋅ 48 = (-23 + 48) ⋅ 71 + 1

37⋅48 = 25⋅71 + 1

Es gilt also: 37⋅48 = 25⋅71 +1

Somit 37⋅48 = 1 mod 71

37 ist also das Inverse von 48 mod 71