Çözüldü Modüler Aritmetikte Denklik (Congruence) - Euclid Algoritması (5 Soru)

a ≠ 0
x, y ∈ Z
(a, m) = 1
ax ≡ ay (mod m) ⇒ x ≡ y ( mod( a / (a, m) ) ve x ≡ y(mod m) olduğunun gösterilmesi:

Yani, x - y ≡ 0 ( mod( a / (a, m) ) ve x - y ≡ 0 (mod m) olduğu şöyle ispatlanabilir;
(a, m) = 1 ⇒ m | a(x - y) <==> m | (x - y)
(a, m) > 1 ⇒ ( a / (a, m), m / (a, m) ) = 1 olup,
m | a(x − y) <==> m / (a, m) | ( a / (a, m) )(x - y) <==> m / (a, m) | (x - y)
---
8x ≡ 11 (mod 35)

8x - 35y = 11 diyofant denklemi için n ∈ Z olmak üzere Öklit Algoritmasıyla;
35 = 8·4 + 3
4 = 3·1 + 1
y = 8n + 7
x = [ 35(8n + 7) + 11 ] / 8 = 35n + 32
x ≡ 32(mod 35)
---
20x ≡ 4 (mod 30)

EBOB(20, 30) = 10
10 ∤ 4, yani 4 sayısı 10 ile bölünemez olduğundan tam sayılar kümesinde çözüm yok.
---
353x ≡ 254 (mod 400)

400 = 353·1 + 47
353 = 47·7 + 24
47 = 24·1 + 23
24 = 23·1 + 1
23 = 23·1 + 0
Sondan başa doğru gidilerek;
1 = 24 − 23 = 24 − (47 − 24) = 2·24 − 47 = 2·(353 − 7·47) − 47 =
2·353 − 15·47 = 2·353 − 15(400 − 353) = 17·353 − 15·400 yazılıp 353^(-1) = 17(Mod 400)

Sonuç olarak x = 17·254 ≡ z(mod 400)
4318 ≡ z(mod 400)
4000 + 318 ≡ z(mod 400)
z = 318
x ≡ 318(mod 400) yani n ∈ Z olmak üzere x = 400n + 318