Algebra va sonlar nazariyasi

Misol 39.1. 7-x = 9 tenglamani Z₁₀ da yeching. Bu yerda a = 7, b = 9 va m = 10 bo‘lib, (7,10) = 1. Yevklid algoritmidan foydalanib 7 • 3 +10 • (-2) = 1 ekanligini hosil qilamiz, ya’ni u = 3, v = -2.
Demak,
x = 3 • 9 = 3^9 = 27 = 7
tenglamaning yechimi bo‘ladi.

Eyler teoremasidan foydalanib yechish usuli. Ma’lumki, (a,m) = 1 bo‘lsa, a^p(m) = 1(modm) bo‘ladi. Endi a • x = b tengla­maning ikkala tomonini a^?(m)—1 ga ko‘paytirsak,

a^v(m1 • a • x = a^-¹ • b,
0^) • x = a^p(“^)—1 • b,

2. 
   x = a^^(m)—1 • b, x = a^^(m)—1 •b.
   

hosil bo‘ladi. Topilgan x element tenglamaning yechimi bo‘ladi.
Misol 39.2. 3-x = 7 tenglamani Z_n da yeching. Ushbu tenglamada (3,11) = 1 bo‘lganligi uchun yuqorida keltirilgan usuldan foydalanamiz. (p(11) = 10 ekanligi uchun
x = 3⁹ • 7 = 27³ • 7 = 5³ • 7 = 125 • 7 = 4 • 7 = 28 = 6
bo‘ladi.
Uzluksiz kasrlardan foydalanish usuli. Ushbu usul bevosita ax = b(mod m) taqqoslama uchun keltiriluvchi usuldir.
Taqqoslamali tenglamada (a,m) = 1 va a > 0 bo‘lsin. U holda
m

• 
  kasrni uzluksiz kasrga yoyib, P_k, Q munosib kasrlarni topamiz.
  

a
Bu munosib kasrlar uchun
PkQk—1 — Pk Q = (—1)^k
tenglik o‘rinli bo‘ladi. P„ = m, Q_n = a bo‘lishini inobatga olsak,
^mQn—1 ^{— P}n—1^a =^(—1)n
tenglikni hosil qilamiz.
Oxirgi tenglikdan aP_n—1 = (—1)^n—1 + mQ_m—1 yoki
aP_n_₁ = (—1)^n—1(mod m) hosil bo‘ladi. Agar ax = b(modm) taqqoslamaning ikkala tomonini
(—1)^n—1 _P_j ga ko‘paytirsak,


269

4k	0	1	1	1	17
Pk	1	1	2	3	53

Demak, P₃ = 3 bundan
x - (-1)³ • 3 • 17(mod53) - -51(mod53) - 2(mod53) yechim hosil bo‘ladi.
Berilgan 105x - 51(mod159) taqqoslamaning yechimlari esa, quyidagilardan iborat bo‘ladi:
x - 2(mod159), x - 55(mod159), x - 108(mod159).
Koeffitsientlarni o‘zgartirish usuli. Amalda taqqoslamali tenglamalarda taqqoslamaning xossalaridan foydalanib, noma’lum oldidagi koeffitsientni yoki b ni o‘zgartirish mumkin. O‘zgartirishni

shunday almashtirish kerakki, natijada o‘ng tomonda hosil bo‘lgan son a ga bo‘linsin. Bu usul gohida yuqoridagi usullarni qo‘llamasdan turib, taqqoslamali tenglamalarning yechimini topishga imkon beradi. Misol 39.4. 9x - 7(mod11) taqqoslamani yeching.

9x - 7(mod11),
9x - (7 +11)(mod11),
9x - 18(mod11).
(9,11) = 1 bo‘lganligi uchun, tenglikni ikki tomonini 9 ga bo‘lib yuborilsa, x - 2(mod11) yechim hosil bo‘ladi.
Misol 39.5. 55x - 35(mod36) taqqoslamani yeching. Taqqoslamaning ikki tomonini 5 ga bo‘lib, so‘ngra koeffitsien- tini o‘zgartirsak,
llx - 7(mod36), llx - (7 - 216)(mod36), llx --209(mod36), x --19(mod36), x - 17(mod36)
kelib chiqadi.
Qoldiqlar haqidagi Xitoy teoremasi. Endi quyidagi taqqoslamalar sistemasini qaraymiz:
x - bj (mod m k, x - b₂ (mod m k,


x - b_k (mod m),
bu yerda, m_x, m₂,..., m_k sonlari jufti-jufti bilan o‘zaro tub sonlar.
Bu sistema bir noma’lumli chiziqli taqqoslamalar sistemasi deyiladi.

2. 
   teorema (Qoldiqlar haqidagi Xitoy teoremasi). Bir
   

noma’lumli chiziqli taqqoslamalar sistemasi berilgan bo‘lib, M_s va M'_s sonlari quyidagicha aniqlangan bo‘lsin:
m • m₂ •... • m_s = M_s • m_s, M_s • M'_s = 1(modm_s).


271

x₀ sonini quyidagicha aniqlaymiz:

x = M1 • m; • b + M2 • м2 • b₂+... + M_k • m; • bk.
U holda
x = x₀(modщ • m₂ •... • щ) taqqoslamani qanoatlantiruvchi barcha x lar to‘plami berilgan sistemaning yechimlari to‘plamiga teng bo‘ladi.
Isbot. M. larning aniqlanishiga ko‘ra, M_s dan farqli barcha M.
lar m_s ga bo‘linadi. Natijada,
x₀ = MM'p_s (mod m_s) = b_s (mod m_s) hosil bo‘ladi. Shu sababli x = x₀ yechim sistemani qanoatlantiradi.
Bundan esa, berilgan sistema quyidagi sistemaga ekvivalent ekanligi kelib chiqadi:
x = x₀ (mod щ), x = x₀ (mod m₂),


x = x (mod щ).
37.8 va 37.9-xossalarga asosan, bu sistema x = x(modщ • m₂ •... • щ) taqqoslamaga teng kuchlidir.
Misol 39.6. Quyidagi sistemani yeching.
x = b (mod 4),
₂(mod 5), x ^ b (mod 7).
Bu yerda M = 35, M₂ = 28, M₃ = 20 bo‘lganligi uchun,
35• 3 = 1(mod4), 28• 2 = 1(mod5), 20• 6 = 1(mod7) ekanligidan M = 3, M₂ = 2, M₃ = 6 bo‘lishini hosil qilamiz. Demak, x = 35 • 3b + 28 • 6b + 20 • 6b = 105bj + 56b + 120b. Yuqoridagi teoremaga ko‘ra berilgan sistema quyidagi tenglamaga teng kuchli:
x = (105b + 56b + 120b )(mod140).
Aytaylik, b =1, b = 3 va b₃ = 2 bo‘lsin, u holda

x₀ = 105 4 + 56 • 3 +120 • 2 bo‘lib, sistemaning quyidagi yechimi hosil bo‘ladi