Um längere Rechnungen zu vermeiden, rechnen wir:

(15001 + 602) mod 3 ≡ (15001 mod 3 + 602 mod 3) mod 3.

15001 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 15001 = 15000+1 = 3 ⋅ 5000 +1.

602 mod 3 ≡ 2 mod 3 kann man relativ leicht bestimmen, weil ja 602 = 600+2 = 3 ⋅ 200 +2.

Somit gilt:

(15001 + 602) mod 3 ≡ (1 + 2) mod 3 ≡ 3 mod 3 ≡ 0 mod 3.

Um längere Rechnungen zu vermeiden, rechnen wir:

(38 ⋅ 31) mod 3 ≡ (38 mod 3 ⋅ 31 mod 3) mod 3.

38 mod 3 ≡ 2 mod 3 kann man relativ leicht bestimmen, weil ja 38 = 36 + 2 = 12 ⋅ 3 + 2 ist.

31 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 31 = 30 + 1 = 10 ⋅ 3 + 1 ist.

Somit gilt:

(38 ⋅ 31) mod 3 ≡ (2 ⋅ 1) mod 3 ≡ 2 mod 3.

Die 32 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: 370¹=370

2: 370²=370¹⁺¹=370¹⋅370¹ ≡ 370⋅370=136900 ≡ 487 mod 659

4: 370⁴=370²⁺²=370²⋅370² ≡ 487⋅487=237169 ≡ 588 mod 659

8: 370⁸=370⁴⁺⁴=370⁴⋅370⁴ ≡ 588⋅588=345744 ≡ 428 mod 659

16: 370¹⁶=370⁸⁺⁸=370⁸⋅370⁸ ≡ 428⋅428=183184 ≡ 641 mod 659

32: 370³²=370¹⁶⁺¹⁶=370¹⁶⋅370¹⁶ ≡ 641⋅641=410881 ≡ 324 mod 659

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

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

248 = 128+64+32+16+8

332²⁴⁸

= 332^{128+64+32+16+8}

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

≡ 186 ⋅ 905 ⋅ 589 ⋅ 340 ⋅ 765 mod 983
≡ 168330 ⋅ 589 ⋅ 340 ⋅ 765 mod 983 ≡ 237 ⋅ 589 ⋅ 340 ⋅ 765 mod 983
≡ 139593 ⋅ 340 ⋅ 765 mod 983 ≡ 7 ⋅ 340 ⋅ 765 mod 983
≡ 2380 ⋅ 765 mod 983 ≡ 414 ⋅ 765 mod 983
≡ 316710 mod 983 ≡ 184 mod 983

Es gilt also: 332²⁴⁸ ≡ 184 mod 983

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

=>89	= 1⋅48 + 41
=>48	= 1⋅41 + 7
=>41	= 5⋅7 + 6
=>7	= 1⋅6 + 1
=>6	= 6⋅1 + 0

also gilt: ggt(89,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= 7-1⋅6
6= 41-5⋅7	eingesetzt in die Zeile drüber:	1	= 1⋅7 -1⋅(41 -5⋅ 7) = 1⋅7 -1⋅41 +5⋅ 7) = -1⋅41 +6⋅ 7 (=1)
7= 48-1⋅41	eingesetzt in die Zeile drüber:	1	= -1⋅41 +6⋅(48 -1⋅ 41) = -1⋅41 +6⋅48 -6⋅ 41) = 6⋅48 -7⋅ 41 (=1)
41= 89-1⋅48	eingesetzt in die Zeile drüber:	1	= 6⋅48 -7⋅(89 -1⋅ 48) = 6⋅48 -7⋅89 +7⋅ 48) = -7⋅89 +13⋅ 48 (=1)

Es gilt also: ggt(89,48)=1 = -7⋅89 +13⋅48

oder wenn man -7⋅89 auf die linke Seite bringt:

1 +7⋅89 = +13⋅48

Es gilt also: 13⋅48 = 7⋅89 +1

Somit 13⋅48 = 1 mod 89

13 ist also das Inverse von 48 mod 89