22-мавзу: биринчи даражали бир номаълумли танқосламаларнинг эчимлари сони ҳАҚидаги теорема. 1-таъриф

22-МАВЗУ: БИРИНЧИ ДАРАЖАЛИ БИР НОМАЪЛУМЛИ
ТАНҚОСЛАМАЛАРНИНГ ЭЧИМЛАРИ СОНИ ҲАҚИДАГИ ТЕОРЕМА.
1-ТАЪРИФ. Ушбу
ax b (modm) (1)
кўринишдаги таққослама бир номаълумли, биранчи даражали таққослама дейилади (бу ерда а ва b– бутун сонлар, m– натурал сон).
2-ТАЪРИФ.Aгap(1) таққосламада x=x₁ бўлганда аx₁b(mod m) такқослама тўғри бўлса, у ҳолда x₁сон (1) таққосламани қаноатлантиради дейилади.
ТЕОРЕМА.Агар (1) таққосламани х₁, сон қаноатлантирса, у ҳолда (1) таққосламани. x₁+mt (t–бутун сон) сонлар системаси қаноатлантиради.
Ҳақиқатан, берилишнга кўра ax₁b(mod m) таққослама тўғри.x₁+mtсонлар системасига тегишли ихтиёрий x₁сонни олайлик. У ҳолда x₂=x₁(modm) бўлиб, бундан 15-мавзудаги 5-хоссага кўра f(х₂)f(х₁)(modm)таққослама келиб чиқади. Бунда f(х₁)f(х₁)(modm)ни эътиборга олсак, f(х₂)0(modm) таққосламага эга бўламиз, яъни х₂ сон (1) таққосламани қаноатлантиради. Демак, х₁+mtсонлар системасидаги ҳар бир сон (1) таққосламаниканоатлантирар экан.
x₁+mtсонлар системаси ёки |x₁|синф ҳам деб юритилади.
3-ТАЪРИФ.Aгap х₁ сон (1) таққосламани қаноатлантирса, у ҳолда синф(1) таққосламанйнг ечами деб аталади.
(1) таққосламани қаноатлантирувчи совларни 0, 1, 2, . . .,m –1сонлар ичидан қидириш керак.
(1) таққосламани ечишнинг қуйидаги иккита ҳолини кўрайлик:
1. (а; m)=1бўлсин. Aгap (1) таққослама ечимга эга бўлса, бу ечим m модуль бўйича чегирмаларнинг бирор синфи бўлади. Маълумки, чегирмаларнинг тўла системасидаги ҳар бир чегирмага битта синф мос келар эди. Демак, (1) да х сон чегирмаларнинг тўла системасини қабул қилар экан. У ҳолда чизиқли форма ҳақидаги теоремага кўра ах ҳам чегирмаларнинг тўла системасини қабул қилади. х нинг бирор х₀ қиймати топиладики, натижада ах₀ чегирма билан b сон битта синфга тегишли бўлади, яъни ax₀b (modm) бўлиб, xx₀ (modm) бўлади. Бу ечим, юқорида айтилганидек, ёки [х₀] кўринишларда ҳам белгиланади.
2.(а; m) = d>1бўлсин. (1) таққосламани унга тенг кучли ах–b= ту (х,уZ) тенглик кўринишда ёзамиз. Бундан ax–my=b бўлиб, (а; m) =d га кўра a/dm/db/d. Демак, агар b d ҳолда, яъни b сон d га бўлинмаса, (1) такқослама ечимга эга бўлмайди.
Фараз қилайлик, b сон d га бўлинсин, яъни b= db₁ бўлсин. Таққосламаларнинг хоссасига асосан (1) нинг иккала қисмини ва модулини d га бўлиб, қуйидагини ҳосил қиламиз:
a₁xb₁(mod т₁).(2)
(2) таққослама (1) таққосламага тенг кучли эканлигини кўрсатамиз. –(2) таққосламанинг ихтиёрий ечими бўлсин. a₁x₁b₁(modт₁) таққосламанинг иккала қисмини ва модулини dгa кўпайтирамиз.
da₁x₁db₁(mod т₁)ax₁b(mod m).
Демак, –(1)таққосламанинг ечими экан. –(1) таққосламанинг ихтиёрий ечими бўлсин. ax₀b(mod m) таққосламанинг икала қисмини ва модулини d сонга бўламиз. У ҳолда a₁x₀b₁(modт₁) таққослама ҳосил бўлади, яьни –(2) таққосламанинг ечими экан. Демак, (1) ва(2) таққосламалар тенг кучли экан. (a₁;m₁) = 1 бўлганидан (1) ҳолга асосан (2) таққослама m₁ модуль бўйича қуйидаги ягона ечимга эга: xх₀(mod т₁) ёки х=х₀+m₁k (kZ).Бy ечим (1) ни ҳам қаноатлантиради, лекин(1) нинг ечимлари шу билан тугамайди. Берилган таққосламанинг ечимларини m модуль бўйича топиш учун қуйидагиларга эътибор берамиз:
х₁,x₁+m₁,..., х₁+ (d–1) т₁ (3)
чегирмаларнинг ҳар бири m, модуль бўйича тенг қолдиқлар бўлиб. m₁d=m модуль бўйича эса турли синфга тегишлидир. Шy турли синфларнинг элементлари
х₁,x₁+m₁,x₁+2m₁,..., х₁+ (d–1) т₁ (4)
дан иборат. Ҳақиқатан, (4) нинг ҳар қандай иккита элементи m модуль бўйича таққосланувчи эмас. (3) синфнинг (4) га кирмаган ҳар бир элементи учун (4) да шундай элемент топиладики, уларнинг айирмаси m₁d–тгa бўлинади. Шунинг учун улар битта синфнинг элементлари ҳисобланади. Демак, (а;m)=d ва (b;m) = d бўлса, (1) таққослама (4) орқали аниқланувчи d та ечимга эга экан. Юқоридагиларга асосан қуйидаги хулосани ёза оламиз:

1. 
   Aгap(а; m)= 1бўлса, (1) нинг ечими мавжуд ва ягонадир.
   

2.(а;m) = d>1бўлганда
а) b/d бўлса, (1) нинг ечкми мавжуд эмас;
б) b d бўлса, (1) таққослама d та ечимга эга.
Мисоллар.1. 3х 7 (mod 11) таққосламани ечинг.
(3; 11)=1 бўлгани учун ечим ягона бўлади. 11 модуль бўйича чегирмаларнинг системаси 0, ±1, +2, ±3, ±4, ±5 дан иборат. Бевосита текшириб кўриш билан x–5 (mod11) ечим эканлигига ишонч ҳосил қйламиз.
2. 5х = 7 (mod 15) таққосламани ечинг.
(5; 15) = 5, лекин 7 5 бўлгани учун бу таққослама ечимга эга эмас,
3. 9х  6 (mod 15) таққосламани ечинг.
(9; 15) = 3 ва 6/3 бўлгани учун таққослама учта ечимга эга. Ҳақиқатан, таққосламани
3х 2(mod5)
шаклида ёзиб оламиз, (3; 5) = 1 бўлгани учун бу таққослама 5 модуль бўйнча ягона x–1 (mod5) ечимга эга. У ҳолда берилган таққосламани –1, –1+5, –1+2∙5сонлар қаноатлантиради. Шунинг учун х–1, 4, 9 (mod 15) берилган таққосламанинг ечимлари бўлади.
23-МАВЗУ:БИРИНЧИ ДАРАЖАЛИ БИР НОМАЪЛУМЛИ ТАҚҚОСЛАМАЛАРНИ ЕЧИШ УСУЛЛАРИ
Ушбу
axb (modm) (1)
кўринишдаги бир номаълумли биринчи даражали таққосламаларни ечишнинг бир қанча усуллари мавжуд.
1. Синаш усули.Бу усулнинг моҳияти шундаки, (1) таққосламадаги х ўрнига m модулга кўра чегирмаларнинг тўла системасидаги барча чегирмалар кетма-кет қўйиб чиқилади. Улардан қайси бири( 1) ни тўғри таққосламага айлантирса, ўша чегирма қатнашган синф ечим ҳисобланади. Биз 22-мавзудаги иккита мисолни шу усулда ечдик. Лекин коэффициентлар етарлича ката бўлганда бу усул унча қулай бўлмайди.
2.Коэффициентларни ўзгартириш усули: Амалий машғулотларда тақкосламаларнинг хоссаларидан фойдаланиб, (1) да номаълум олдидаги коэффициентни ва bни шундай ўзгартириш керакки, натижада таққосламанинг ўнг томонида ҳосил бўлган сон ах ҳаднинг коэффициентига бўлинсин.
1-мисол. 7х 5 (mod9) таққосламани ечинг.
7х 5+ 9 (mod9),
7х 14 (mod9).
(7;14) = 7 ва (7; 9) = 1 бўлганидан х  2 (mod9) ечим келиб чиқади.
2-мисол.17x  25(mod28) таққосламани ечинг.
17x+28x 25(mod28),
45х25 (mod28).
Бундан 9х 5 (mod28),
9х 5 –140 (mod28) –135 (mod28),
9х –135 (mod 28), x–15 (mod 28),.
х 13(mod 28) ечим ҳосил бўлади.
3.Эйлер теоремасидан фойдаланиш усули. Маълумки, (а;m) = 1 бўлса, у ҳолда а^φ(m)1 (modm) таққослама ўринли эди. Бундан с^φ(m)∙b b(mod m) таққосламани ёзиш мумкин. Охирги таққосламани ахb(modm) таққослама билан солиштириб, ха^φ(m)∙b(modm) эканига ишонч ҳосил қиламиз. Мисоллар ечишда а^φ(m)∙b– ифодани m модуль бўйича энг кичик мусбат чегирмага келтириш лозим.
3-мисол.3х7 (mod11) таққосламани ечинг.
x3^φ(11)-1∙7 (mod11), φ(11)= 10,
3² 9–2 (mod11), 3⁴4 (mod11),
3³= 121(mod11)бўлганидан x= 3⁹∙7= 286(mod11), х6(mod11)ечим ҳосил бўлади.
Таққосламанинг модули етарлича катта бўлса, қуйидаги усул анча фойдалидир.
4.Узлуксиз касрлардан фойдаланиш у с у л и.
Ушбу
ахb(mod m) (1)
таққослама берилган бўлиб, (а; m) = l ва а>0 бўлсин.
касрни узлуксиз касрга ёйиб, унинг муносиб касрларини каби белгилаймиз. қисқармас каср бўлганидан _n= m, Q_n=а бўлади, у ҳолда _nQ_n-1– _n-1Q_n=(–1)ⁿ тенглик – P_n-1a=(–1)ⁿ шаклни олади. Охирги тенгликдан a P_n-1= – (–1)ⁿ +mQ_n-1 ёки a P_n-1 – (–1)^n-1 (mod m) ҳосил бўлади. Охирги таққосламанинг иқкала қисмини (–1)^n-1b ва кўпайтириб,
а(–1)^n-1bP_n-1 b (modm) (2)
таққосламага эга бўламиз. (1) ва (2) ни солиштириб,
x (–l)^n-1bP_n-1 (modm) (3)
таққосламани ҳосил қиламиз. Бу ерда P_n-1 сон касрнинг(п–1) -муносиб касрининг суратидан иборат. (1) таққослама ягоқа ечимга эга бўлгани учун (3) ечим (1) нинг ечими бўлади.


4-мисол. 285х  117(mod 924) таққосламани ечинг.
(285;924) = 3, 177/3
бўлганидан таққосламанинг модули ва иккала қисмини 3 га бўлиб, ушбу
95х  59 (mod 308)
таққосламани ҳосил қиламиз. Энди касрни муносиб касрларга ёямиз. Бунинг учун кетма-кет бўлишни қуйидагича бажарамиз:
308 = 95  3 + 23,
95 = 23  4 + 3,
23 = 3  7 + 2,
3 = 2 1 + 1,
2=12
q₁ = 3, q₂ = 4, q₃=7, q₄ = 1, q₅ = 2,
Қуйидаги жадвални тузамиз:

qk		3	4	7	1	2
Pk	1	3	13	94	107	308

Демак, P_n-1=P₄= 107 экан. Бундан

х  (–1)⁴ 107  59 (mod 308)
ёки
х  153 (mod308).
У ҳолда берилган таққослама ечимлари қуйидагилар бўлади:
х  153, 461, 769 (mod 924).