Um längere Rechnungen zu vermeiden, rechnen wir:

(2003 - 1599) mod 4 ≡ (2003 mod 4 - 1599 mod 4) mod 4.

2003 mod 4 ≡ 3 mod 4 kann man relativ leicht bestimmen, weil ja 2003 = 2000+3 = 4 ⋅ 500 +3.

1599 mod 4 ≡ 3 mod 4 kann man relativ leicht bestimmen, weil ja 1599 = 1500+99 = 4 ⋅ 375 +99.

Somit gilt:

(2003 - 1599) mod 4 ≡ (3 - 3) mod 4 ≡ 0 mod 4.

Um längere Rechnungen zu vermeiden, rechnen wir:

(37 ⋅ 49) mod 9 ≡ (37 mod 9 ⋅ 49 mod 9) mod 9.

37 mod 9 ≡ 1 mod 9 kann man relativ leicht bestimmen, weil ja 37 = 36 + 1 = 4 ⋅ 9 + 1 ist.

49 mod 9 ≡ 4 mod 9 kann man relativ leicht bestimmen, weil ja 49 = 45 + 4 = 5 ⋅ 9 + 4 ist.

Somit gilt:

(37 ⋅ 49) mod 9 ≡ (1 ⋅ 4) mod 9 ≡ 4 mod 9.

Die 8 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: 378¹=378

2: 378²=378¹⁺¹=378¹⋅378¹ ≡ 378⋅378=142884 ≡ 108 mod 661

4: 378⁴=378²⁺²=378²⋅378² ≡ 108⋅108=11664 ≡ 427 mod 661

8: 378⁸=378⁴⁺⁴=378⁴⋅378⁴ ≡ 427⋅427=182329 ≡ 554 mod 661

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

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

247 = 128+64+32+16+4+2+1

151²⁴⁷

= 151^{128+64+32+16+4+2+1}

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

≡ 79 ⋅ 107 ⋅ 193 ⋅ 268 ⋅ 310 ⋅ 61 ⋅ 151 mod 379
≡ 8453 ⋅ 193 ⋅ 268 ⋅ 310 ⋅ 61 ⋅ 151 mod 379 ≡ 115 ⋅ 193 ⋅ 268 ⋅ 310 ⋅ 61 ⋅ 151 mod 379
≡ 22195 ⋅ 268 ⋅ 310 ⋅ 61 ⋅ 151 mod 379 ≡ 213 ⋅ 268 ⋅ 310 ⋅ 61 ⋅ 151 mod 379
≡ 57084 ⋅ 310 ⋅ 61 ⋅ 151 mod 379 ≡ 234 ⋅ 310 ⋅ 61 ⋅ 151 mod 379
≡ 72540 ⋅ 61 ⋅ 151 mod 379 ≡ 151 ⋅ 61 ⋅ 151 mod 379
≡ 9211 ⋅ 151 mod 379 ≡ 115 ⋅ 151 mod 379
≡ 17365 mod 379 ≡ 310 mod 379

Es gilt also: 151²⁴⁷ ≡ 310 mod 379

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