Um längere Rechnungen zu vermeiden, rechnen wir:

(2395 + 296) mod 6 ≡ (2395 mod 6 + 296 mod 6) mod 6.

2395 mod 6 ≡ 1 mod 6 kann man relativ leicht bestimmen, weil ja 2395 = 2400-5 = 6 ⋅ 400 -5 = 6 ⋅ 400 - 6 + 1.

296 mod 6 ≡ 2 mod 6 kann man relativ leicht bestimmen, weil ja 296 = 300-4 = 6 ⋅ 50 -4 = 6 ⋅ 50 - 6 + 2.

Somit gilt:

(2395 + 296) mod 6 ≡ (1 + 2) mod 6 ≡ 3 mod 6.

Um längere Rechnungen zu vermeiden, rechnen wir:

(41 ⋅ 60) mod 4 ≡ (41 mod 4 ⋅ 60 mod 4) mod 4.

41 mod 4 ≡ 1 mod 4 kann man relativ leicht bestimmen, weil ja 41 = 40 + 1 = 10 ⋅ 4 + 1 ist.

60 mod 4 ≡ 0 mod 4 kann man relativ leicht bestimmen, weil ja 60 = 60 + 0 = 15 ⋅ 4 + 0 ist.

Somit gilt:

(41 ⋅ 60) mod 4 ≡ (1 ⋅ 0) mod 4 ≡ 0 mod 4.

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

2: 292²=292¹⁺¹=292¹⋅292¹ ≡ 292⋅292=85264 ≡ 465 mod 593

4: 292⁴=292²⁺²=292²⋅292² ≡ 465⋅465=216225 ≡ 373 mod 593

8: 292⁸=292⁴⁺⁴=292⁴⋅292⁴ ≡ 373⋅373=139129 ≡ 367 mod 593

16: 292¹⁶=292⁸⁺⁸=292⁸⋅292⁸ ≡ 367⋅367=134689 ≡ 78 mod 593

32: 292³²=292¹⁶⁺¹⁶=292¹⁶⋅292¹⁶ ≡ 78⋅78=6084 ≡ 154 mod 593

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

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

215 = 128+64+16+4+2+1

514²¹⁵

= 514^{128+64+16+4+2+1}

= 514¹²⁸⋅514⁶⁴⋅514¹⁶⋅514⁴⋅514²⋅514¹

≡ 167 ⋅ 564 ⋅ 243 ⋅ 37 ⋅ 357 ⋅ 514 mod 601
≡ 94188 ⋅ 243 ⋅ 37 ⋅ 357 ⋅ 514 mod 601 ≡ 432 ⋅ 243 ⋅ 37 ⋅ 357 ⋅ 514 mod 601
≡ 104976 ⋅ 37 ⋅ 357 ⋅ 514 mod 601 ≡ 402 ⋅ 37 ⋅ 357 ⋅ 514 mod 601
≡ 14874 ⋅ 357 ⋅ 514 mod 601 ≡ 450 ⋅ 357 ⋅ 514 mod 601
≡ 160650 ⋅ 514 mod 601 ≡ 183 ⋅ 514 mod 601
≡ 94062 mod 601 ≡ 306 mod 601

Es gilt also: 514²¹⁵ ≡ 306 mod 601

Berechnung des größten gemeinsamen Teilers von 53 und 20

=>53	= 2⋅20 + 13
=>20	= 1⋅13 + 7
=>13	= 1⋅7 + 6
=>7	= 1⋅6 + 1
=>6	= 6⋅1 + 0

also gilt: ggt(53,20)=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= 13-1⋅7	eingesetzt in die Zeile drüber:	1	= 1⋅7 -1⋅(13 -1⋅ 7) = 1⋅7 -1⋅13 +1⋅ 7) = -1⋅13 +2⋅ 7 (=1)
7= 20-1⋅13	eingesetzt in die Zeile drüber:	1	= -1⋅13 +2⋅(20 -1⋅ 13) = -1⋅13 +2⋅20 -2⋅ 13) = 2⋅20 -3⋅ 13 (=1)
13= 53-2⋅20	eingesetzt in die Zeile drüber:	1	= 2⋅20 -3⋅(53 -2⋅ 20) = 2⋅20 -3⋅53 +6⋅ 20) = -3⋅53 +8⋅ 20 (=1)

Es gilt also: ggt(53,20)=1 = -3⋅53 +8⋅20

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

1 +3⋅53 = +8⋅20

Es gilt also: 8⋅20 = 3⋅53 +1

Somit 8⋅20 = 1 mod 53

8 ist also das Inverse von 20 mod 53