Um längere Rechnungen zu vermeiden, rechnen wir:

(213 - 210) mod 7 ≡ (213 mod 7 - 210 mod 7) mod 7.

213 mod 7 ≡ 3 mod 7 kann man relativ leicht bestimmen, weil ja 213 = 210+3 = 7 ⋅ 30 +3.

210 mod 7 ≡ 0 mod 7 kann man relativ leicht bestimmen, weil ja 210 = 210+0 = 7 ⋅ 30 +0.

Somit gilt:

(213 - 210) mod 7 ≡ (3 - 0) mod 7 ≡ 3 mod 7.

Um längere Rechnungen zu vermeiden, rechnen wir:

(38 ⋅ 48) mod 10 ≡ (38 mod 10 ⋅ 48 mod 10) mod 10.

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

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

Somit gilt:

(38 ⋅ 48) mod 10 ≡ (8 ⋅ 8) mod 10 ≡ 64 mod 10 ≡ 4 mod 10.

Die 16 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: 831¹=831

2: 831²=831¹⁺¹=831¹⋅831¹ ≡ 831⋅831=690561 ≡ 484 mod 853

4: 831⁴=831²⁺²=831²⋅831² ≡ 484⋅484=234256 ≡ 534 mod 853

8: 831⁸=831⁴⁺⁴=831⁴⋅831⁴ ≡ 534⋅534=285156 ≡ 254 mod 853

16: 831¹⁶=831⁸⁺⁸=831⁸⋅831⁸ ≡ 254⋅254=64516 ≡ 541 mod 853

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

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

119 = 64+32+16+4+2+1

371¹¹⁹

= 371^{64+32+16+4+2+1}

= 371⁶⁴⋅371³²⋅371¹⁶⋅371⁴⋅371²⋅371¹

≡ 68 ⋅ 215 ⋅ 407 ⋅ 201 ⋅ 84 ⋅ 371 mod 457
≡ 14620 ⋅ 407 ⋅ 201 ⋅ 84 ⋅ 371 mod 457 ≡ 453 ⋅ 407 ⋅ 201 ⋅ 84 ⋅ 371 mod 457
≡ 184371 ⋅ 201 ⋅ 84 ⋅ 371 mod 457 ≡ 200 ⋅ 201 ⋅ 84 ⋅ 371 mod 457
≡ 40200 ⋅ 84 ⋅ 371 mod 457 ≡ 441 ⋅ 84 ⋅ 371 mod 457
≡ 37044 ⋅ 371 mod 457 ≡ 27 ⋅ 371 mod 457
≡ 10017 mod 457 ≡ 420 mod 457

Es gilt also: 371¹¹⁹ ≡ 420 mod 457

Berechnung des größten gemeinsamen Teilers von 97 und 52

=>97	= 1⋅52 + 45
=>52	= 1⋅45 + 7
=>45	= 6⋅7 + 3
=>7	= 2⋅3 + 1
=>3	= 3⋅1 + 0

also gilt: ggt(97,52)=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-2⋅3
3= 45-6⋅7	eingesetzt in die Zeile drüber:	1	= 1⋅7 -2⋅(45 -6⋅ 7) = 1⋅7 -2⋅45 +12⋅ 7) = -2⋅45 +13⋅ 7 (=1)
7= 52-1⋅45	eingesetzt in die Zeile drüber:	1	= -2⋅45 +13⋅(52 -1⋅ 45) = -2⋅45 +13⋅52 -13⋅ 45) = 13⋅52 -15⋅ 45 (=1)
45= 97-1⋅52	eingesetzt in die Zeile drüber:	1	= 13⋅52 -15⋅(97 -1⋅ 52) = 13⋅52 -15⋅97 +15⋅ 52) = -15⋅97 +28⋅ 52 (=1)

Es gilt also: ggt(97,52)=1 = -15⋅97 +28⋅52

oder wenn man -15⋅97 auf die linke Seite bringt:

1 +15⋅97 = +28⋅52

Es gilt also: 28⋅52 = 15⋅97 +1

Somit 28⋅52 = 1 mod 97

28 ist also das Inverse von 52 mod 97