Matematika-informatika kafedrasi

4-§ Birinchi darjali taqqoslamalar va ularni yechish usullari.
1-TA`RIF. Ushbu 𝑎𝑥 ≡ (𝑚𝑜𝑑𝑚) (1) ko`rinishdagi taqqoslama bir noma`lumli birinchi darajali taqqoslama deyiladi. (bu erda a va b-butun sonlar, m-natural son) 2-TA`RIF. Agar (1) taqqoslamada 𝑥 = 𝑥0 bo`lganda 𝑎𝑥0 ≡ (𝑚𝑜𝑑𝑚) taqqoslama to`g`ri bo`lsa, u holda 𝑥0 son taqqoslamani qanoatlantiradi deyiladi. 3-TA`RIF. 𝑚 modul` bo`yicha taqqoslamaning yechimlar soni deb, bu taqqoslamaning m modul` bo`yicha chegirmalarning to`liq sistemadagi yechimlar soniga aytiladi. Agar a son (1) taqqoslamani qanoatlantirsa u holda m modul` bo`yicha a bilan taqqoslanuvchi ∀ 𝑏 son ham bu taqqoslamani qanoatlantiradi, bunday 2 ta yechim bitta deb qaraladi. Misol. 5𝑥 ≡ 3(𝑚𝑜𝑑6), 0, 1, 2, 3, 4, 5 𝑥 = 3(𝑚𝑜𝑑6) 𝑥0 = 3 + 6𝑡, ∀𝑡 ∈ ℤ 𝑥0 = 9, 15, … sonlar ham bu taqqoslamani qanoatlantiradi. TEOREMA. Agar (𝑎, 𝑚) = 1 bo`lsa, u holda (1) taqqoslama yagona yechimga ega bo`ladi. ISBOTI. m modul` bo`yicha chegirmalarning to`la sistemasi 𝑥1, 𝑥2, … , 𝑥𝑚 bo`lsin, u holda 𝑎𝑥1, 𝑎𝑥2, … , 𝑎𝑥𝑚 (2) ham chegirmalarning to`la sistemasi bo`lishi ma`lum. Agar (1) da 𝑥 o`rniga ketma ket (2) dagi chegirmalarni qo`yib ko`rsak, u holda bu taqqoslamaning chap qismi chegirmalarning to`la sistemasidagi barcha qiymatlardan o`tadi. Bu esa bitta va faqat bitta 𝑥𝑖 son uchun 𝑎𝑥𝑖 sonning b songa tegishli bo`lgan chegirma sinfiga tegishli bo`lishini bildiradi, bunda 𝑎𝑥𝑖 ≡ (𝑚𝑜𝑑𝑚) bo`ladi. Demak, agar (𝑎, 𝑚) = 1 bo`lsa, (1) taqqoslama yagona bo`lgan 𝑥 = 𝑥(𝑚𝑜𝑑𝑚) yoki 𝑥 = 𝑥𝑖 + 𝑚𝑡, 𝑡 ∈ ℤ yechimga ega bo`ladi. TEOREMA. Agar (𝑎, 𝑚) = 𝑑 > 1 va 𝑏 son 𝑑 ga bo’linmasa, u holda 𝑎𝑥 ≡ (𝑚𝑜𝑑𝑚) taqqoslama yechimga ega bo`lmaydi. ISBOTI. Faraz qilaylik, 𝑎𝑥 ≡ (𝑚𝑜𝑑𝑚) taqqoslama uchun 𝑚 modul` bo`yicha 𝑥1 sinf yechim bo`lsin va 𝑥1 ∈ 𝑥̅̅1̅ bo`lsin, u holda 𝑎𝑥1 ≡ 𝑏(𝑚𝑜𝑑𝑚) yoki 𝑎𝑥1 − 𝑏 = 𝑚𝑡, 𝑡 ∈ ℤ bo`ladi. 𝑎 ⋮ 𝑑 ∧ 𝑚 ⋮ 𝑑 dan 𝑏 ⋮ 𝑑 kelib chiqadi. Bunday bo`lishi mumkin emas, shartga ko`ra 𝑏 son 𝑑 ga bo’linmaydi. Demak, teorema isbotlandi. TEOREMA. Agar (𝑎, 𝑚) = 𝑑 > 1 va 𝑏 son 𝑑 ga bo’linsa, u holda 𝑎𝑥 ≡ (𝑚𝑜𝑑𝑚) taqqoslama 𝑑 ta turli yechimlarga ega bo`ladi. Bu yechim 𝑚 𝑑 modul` bo`yicha bitta sinfni tashkil qiladi. ISBOTI. Shartga ko`ra 𝑎, 𝑏 va 𝑚 sonlar 𝑑 ga bo`linadi. 𝑎 = 𝑎1𝑑, 𝑏 = 𝑏1𝑑 ∧ 𝑚 = 𝑚1𝑑 (1) ni 𝑑 ga bo`lib, unga teng kuchli bo`lgan 𝑎𝑥1 ≡ 𝑏1(𝑚𝑜𝑑𝑚1) (4) taqqoslamaga ega bo`lamiz. Haqiqatan 𝑥 = 𝛼 son (4) ni qanoatlantirsa, u holda 𝑎𝛼 ≡ (𝑚𝑜𝑑𝑚) taqqoslamaga ega bo`lamiz, uning ikkala qismini va modulni 𝑑 ga bo`lib, 𝑎1𝛼 = 𝑏1(𝑚𝑜𝑑𝑚1) hosil bo`ladi. Demak, 𝛼 (4) ni qanoatlantiradi. Aksincha, 𝑥 = 𝛽 butun son 𝑎1𝛽 ≡ 𝑏1(𝑚𝑜𝑑𝑚1) taqqoslamani qanoatlantirsin. Bu taqqoslamaning ikkala qismini va modulni 𝑑 ga ko`paytirib, 𝑎𝛽 ≡ (𝑚𝑜𝑑𝑚) taqqoslamani hosil qilamiz. Demak, 𝛽 (1) ni qanoatlantiradi. Shunday qilib (1) va (4) teng kuchli ekan. (4) dagi (𝑎, 𝑚1 ) = 1, shuning uchun bu taqqoslama 𝑥 = 𝑥0 (𝑚𝑜𝑑𝑚) ∨ 𝑥 = 𝑥0 + 𝑚𝑡, (𝑡 ∈ 𝑡) yagona echimga ega, bu erda 𝑥0 𝑚 modul` bo`yicha manfiymas eng kichik chegirma bo`lsin yoki … 𝑥0 − 2𝑚1, 𝑥0 − 𝑚1, 𝑥0, 𝑥0 + 𝑚, 𝑥0 + 2𝑚1, … , 𝑥0 + (𝑑 − 1)𝑚1, 𝑥0 + 𝑑𝑚1 , 𝑥0 + (𝑑 + 1)𝑚1, … (5) (5) dagi har bir chegirma (4) ni qanoatlantiradi va demak, (1) ni ham qanoatlantiradi. 𝑚1 = 𝑚 𝑑 modul` bo`yicha (5) dagi hamma sonlar bitta sinfga tegishli, lekin 𝑚 = 𝑚1𝑑 modul` bo`yicha ular turli sinflarga tegishli bo`ladi, bu sinflarning chegirmalari esa (6) 𝑥0, 𝑥0 + 𝑚1, 𝑥0 + 2𝑚1, … , 𝑥0 + (𝑑 − 2)𝑚1, 𝑥0 + (𝑑 − 1)𝑚1 Demak, (1) m modul` bo`yicha 𝑑 ta turli echimga ega bo`ladi: 𝑥 ≡ 𝑥0 (𝑚𝑜𝑑𝑚), 𝑥 ≡ 𝑥0 + 𝑚1(𝑚𝑜𝑑𝑚) 𝑥 ≡ 𝑥0 + 2𝑚1 (𝑚𝑜𝑑𝑚), … , 𝑥 ≡ 𝑥0 + (𝑑 − 1)𝑚1(𝑚𝑜𝑑𝑚) bu erda 𝑥0 −(3) taqqoslamaning yechimi bo`lgan sinfning eng kichik manfiymas chegirmasi. Misol. 3𝑥 ≡ 6(𝑚𝑜𝑑9) (3,6) = 3 ∧ 6 ⋮ 3 =2 3 ta yechimga ega. 𝑥 = 2(𝑚𝑜𝑑3) Demak, berilgan taqqoslamaning barcha yechimlari 𝑥 = 2(𝑚𝑜𝑑9), 𝑥 = 2 + 3(𝑚𝑜𝑑9) ≡ 5(𝑚𝑜𝑑9) 𝑥 ≡ 2 + 3 ∙ 2(𝑚𝑜𝑑𝑚) ≡ 8(𝑚𝑜𝑑9) bo`ladi. TEOREMA. Agar (𝑎, 𝑚) = 1 bo`lsa, u holda 𝑎𝑥 ≡ (𝑚𝑜𝑑𝑚) taqqoslamaning yechimi 𝑥 ≡ 𝑏𝑎 𝜑(𝑚)−1 (𝑚𝑜𝑑𝑚) bo`ladi. ISBOTI. (𝑎, 𝑚) = 1 bo`lgani uchun Eyler teoremasiga ko`ra 𝑎 (𝑚) ≡ 1(𝑚𝑜𝑑𝑚). Bundan 𝑎 𝜑(𝑚) ∙ 𝑏 = 𝑏(𝑚𝑜𝑑𝑚) 𝑎 ∙ 𝑎 𝜑(𝑚)−1 ∙ 𝑏 = 𝑏(𝑚𝑜𝑑𝑚) (3) Demak, (1) ∧ (3) ni solishtirsak, 𝑥 = 𝑎 𝜑(𝑚)−1 ∙ 𝑏(𝑚𝑜𝑑𝑚) yechimi ekani ko`rinadi. Misol. 5𝑥 ≡ 3(𝑚𝑜𝑑6) (5,6) = 1 bo`lgani uchun 𝑥 = 3 ∙ 5 𝜑(6)−1 (𝑚𝑜𝑑𝑚) ≡ 3 ∙ 5(𝑚𝑜𝑑𝑚) ≡ 15 ≡ 3(𝑚𝑜𝑑𝑚). Sinash usuli. Bu usulning mohiyati shundaki (1) taqqoslamadagi 𝑥 o`rniga 𝑚 modulga ko`ra chegirmalarning to`la sistemasidagi barcha chegirmalar ketma-ket qo`yib chiqiladi. Ulardan qaysi biri (1) ni to`g`ri taqqoslamaga aylantirsa, o`sha chegirma qatnashgan sinf yechim hisoblanadi. Lekin koeffitsient yetarlicha katta bo`lganda bu usul qulay emas.