«Bir belgisizli birinshi dárejeli salıstırmalardı sheshiw»

II.2 Birinshi dárejeli salıstırmalar sistemaları
Bir belgisizli hár qıylı modulli birinshi dárejeli salıstırmalar sistemasınıń ulıwma kórinisi tómendegiden ibarat:

Bul sistema sheshimin tabıwdıń ulıwma usılı tómendegishe: dáslep sistemanıń birinshi salıstırmasınıń sheshimi tabıladı, bul jerde modul boyınsha teris bolmaǵan eń kishi yamasa absolyut mánisi tárepinen eń kishi shegirmeden ibarat, bul sheshimdi sanlar klası formasında jazıp alınadı:
. (2)
(Eger birinshi salıstırma sheshimge iye bolmasa, berilgen sistema sheshimge iye bolmaydı).
Soń x tiń (2) degi mánisi sistemanıń ekinshi salıstırmasına qoyılıp, (3)
salıstırma payda etiledi. (3) salıstırmadan t nıń sanlar klası formasındaǵı

kórinisi tabılıp, ol (2) teńlikke qoyıladı hám x tiń jańa mánisi esaplanadı. (Eger (3) salıstırma sheshimge iye bolmasa, berilgen sistema da sheshimge iye bolmaydı).
Nátiyjede x tiń sanlar klası formasında jazılǵan hám berilgen sistemanıń dáslepki eki salıstırmanı qanaatlandıratuǵın mánisi payda boladı. x tiń tabılǵan mánisi úshinshi salıstırmaǵa qoyılıp, payda bolǵan salıstırma t₁ ge qarata sheshiledi hám t₁ diń sanlar klası formasında jazılǵan mánisi x tiń ańlatpasına qoyıladı, soń x tiń bul mánisi tórtinshi salıstırmaǵa qoyıladı hám sol tárizde sistemanıń aqırǵı salıstırmasına shekem sheshiledi. x tiń aqırǵı mánisi berilgen sistemanıń sheshiminen ibarat boladı.
Berilgen sistemanı sheshiwden aldın hár bir salıstırmanı bólek sheship, sistema tómendegi kóriniske keltirip alınadı:
(4)
Soń joqarıdaǵı usıl qollanıladı.
Eger (1) sistemanıń salıstırmaları ushın (a_i, m_i) = d_i hám d_i|b_i hám bolsa, onda har bir i-nshi salıstırmanıń aǵzaların hám modulın ge qısqartıp, (1) sistemaǵa teń kúshli bolǵan tómendegi sistema payda etiledi:
(5)
Bul sistemanıń salıstırmaların x ke qarata sheship, (5) sistemanıń sheshimin tómendegi sistemanıń sheshimine keltiriw múmkin:
(6)
Eger (4) sistemada m₁, m₂,..., m_n modullar jup-jubı menen óz-ara ápiwayı bolsa, i ≠ j da (m_i, m_j) = 1 bolsa, onda onıń sheshimin tómendegi formula menen tabıw múmkin:
, (7)
Bul jerde M = [m₁, m₂ ,..., m_n] hám y₁, y₂ ,..., y_n lar
Salıstırmalardıń sheshimlerinen ibarat. Sistemanıń sheshimi x ≡ x₀ (mod M) salıstırmadan ibarat boladı.
Eger modullar jup-jubı menen óz-ara ápiwayı bolsa, bul usıl menen (6) sistemanı da sheshiw múmkin.
Mısal 1. Tómendegi salıstırmalar sistemasın sheshiń.

Sheshiliwi. Birinshi salıstırmadan

Di payda etemiz. x tiń bul mánisin ekinshi salıtırmaǵa qoyamız: 16t + 13 ≡ 3 (mod 10), yamasa 16t + 10 ≡ 0 (mod 10), Bul jerden 8t ≡ 0 (mod 5), yamasa 16t ≡ 0 (mod 5) ni hosil qilamiz. Demek, t = 5t_1. t = 5t₁ ni x = 16t + 13 ańlatpaǵa qoyamız: x = 16⋅5t₁ + 13 = 80t₁ + 13.
x tiń tabılǵan mánisin úshinshi salıstırmaǵa qoyamız: 80t₁ + 13 ≡ 9 (mod 14), yamasa 80t₁ ≡ - 4 (mod 14), bul jerden 80t₁ ≡ 10 (mod 14), yamasa 40t₁ ≡ 5 (mod 7), yamasa 8t₁ ≡ 1 (mod 7), bu yerdan t₁ ≡ 1 (mod 7), ya’ni, t₁ = 7t₂ + 1.
t₁ = 7t₂ + 1 ni x = 80t₁ + 13ańlatpaǵa qoyıp, x=80(70t₂ + 1) + 13 = 560t₂ + 93 ni payda etemiz. Solay etip, x ≡ 93 (mod 560).
Tekseriw: 93–13 ayırma 16 ǵa bo’linedi; 93–13 ayırma 10 ǵa bo’linedi; 93–9 ayırma 14 ga bólinedi.
Esletpe. 16t ≡ 0 (mod 10) salıstırmanı sheshiwde biz 8t ≡ 0(mod 5) salıstırmanı payda ettik, onıń sheshimi t ≡ 0 (mod 5), yamasa t = 5t₁ berilgen salıstırmanıń x = 80t₁ + 13 sheshimine alıp keldi. Biraq 16t ≡ 0 (mod 10) salıstırmanıń ekinshi t ≡ 5 (mod 10), yamasa t = 10t₁ + 5 sheshimi de bar (sebebi, d = (16, 10) = 2). Bul sheshimdi x = 16t + 13 ańlatpaǵa qoyıp, x = 16(10t₁ + 5) +13 = 160t₁ + 93 sheshimdi payda etemiz. Biraq 93 ≡ 13 (mod 80) bolǵanlıǵı ushın, yaǵnıy 93 hám 13 sanlari 80 modul boyınsha bir klassqa tiyisli bolǵanlıǵı ushın x tiń bul mánisine sáykes bolǵan sheshim qaralmaydı.
Bul esletpeden (1-mısal) eger sistemanıń qálegen bir salıstırması yamasa t₁ ge qarata qálegen bir salıstırma m modul boyınsha d dana sheshimge iye bolsa, onda sistemanıń sheshimi tabıw ushun d dana sheshimge iye bolǵan salıstırma sheshimin oǵan teń kúshli bolǵan m/d modul boyınsha salıstırma sheshimi menen almastırıw jeterli boladı.
Mısal 2. Salıstırmalar sistemasın sheshiń:

Sheshiliwi. Sistemanıń hár bir salıstırmasın bólek sheship, bul sistemaǵa teń kúshli bolǵan tómendegi sistemanı payda etemiz:

Bul sistemanıń modulları jup-jubı menen óz-ara ápiwayı sanlardan ibarat bolǵanlıǵı ushın onıń sheshimin (7) formula menen tabıw múmkin.
M = [11, 7, 5] = 385, , ,
Sanlardı tawıp, tómendegi salıstırmalardı dúzemiz:
35u₁ ≡1 (mod 11), 55u₂ ≡1 (mod 7), 77u₃ ≡1 (mod 5),
Bul jerden u₁ = 6, u₂ = - 1, u₃ = 3 larni hosil qilamiz.
Endi (7) formuladan tómendegini payda etemiz:
x₀ = 35⋅6⋅2 + 55⋅ (-1) ⋅5 + 77⋅3⋅4 = 1069 ≡299 (mod 385).
Solay etip, x ≡ 299 (mod 385).
Mısal 3. Salıstırmalar sistemasın sheshiń:

Sheshiliwi. Berilgen sistemanıń úshinshi salıstırmasında (3, 12) = 3, biraq 8 sanı 3 ke bólinbeydi, sonıń ushın bul salıstırma da berilgen sistemada sheshimge iye emes.
Mısal 4. Salıstırmalar sistemasın sheshiń.

Sheshiliwi. Sistemanıń dáslepki eki salıstırması x ≡ -1 (mod 3) hám
x ≡ -1 (mod 2) salıstırmalarǵa teń kúshli, sonıń ushın olardı úshinshi salıstırmanıń nátiyjesi bolǵanlıǵı ushın taslap jiberilse boladı. Solay etip, sistema úshinshi salıstırmasınıń sheshimi sistemanıń da sheshimi boladı, yaǵnıy,
x ≡-1≡5(mod 6).
Mısal 5. 2, 3, 4, 5, 6 hám 7 sanlarına bólingende sáykes túrde 1, 2, 3, 4, 5 hám 0 qaldıq payda bolatuǵın sandı tabıń.
Sheshiliwi. Másele tómendegi salıstırmalar sistemasına keltiriledi:

x ≡ 1 (mod 2) yamasa x ≡ 3 (mod 2) salıstırma x ≡ 3 (mod 4) salıstırmanıń nátiyjesi sıpatında taslap jiberiliwi múmkin. Tap sonday x ≡ 2 (mod 3) salıstırma da alnbaydı.
Solay etip, tómendegi sistemanı payda etemiz:

Bul sistemanı sheship, x ≡ 119 (mod 420) nı payda etemiz.
Mısal 6. Tómendegi salıstırma sheshimge iye bolatuǵın a nıń mánislerin tabıń:

Sheshiliwi. Birinshi salıstırmadan x = 18t + 5 ti payda etemiz. x tiń bul mánisin ekinshi salıstırmaǵa qoyıp, t nıń mánisin tabamız:
18t + 5 ≡ 8 (mod 21), yamasa 18t ≡ 3 (mod 21), yamasa 6t ≡ 1 (mod 7),
t ≡ 6 (mod 7). t ≡ -1 (mod 7) ni alıw qolaylıraq, bul jerden t = 7t₁ – 1. Bul mánisti x tiń ańlatpasına qoyıp, x = 16 (7t₁ – 1) = 5 = 126t₁ – 13.
x tıń payda etilgen mánisin sistemanıń úshinshi salıstırmaǵa qoyamız:
126t₁ – 13 ≡ a (mod 35), t.ye. 21t₁ ≡ a = 13 (mod 35).
(21, 35) = 7 bolanlıǵı ushın aqırǵı salıstırma sheshimge iye bolıwı ushın a + 13 ≡ 0 (mod 7) salıstırma sheshimge iye bolıwı kerek, bul jerden a ≡ 1 (mod 7).
Solay etip, berilgan sistema a ≡ 1 (mod 7) bolǵanda sheshimge iye.