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


Download 0.5 Mb.
bet1/7
Sana20.09.2023
Hajmi0.5 Mb.
#1681969
  1   2   3   4   5   6   7
Bog'liq
algebra 22 3411


22-МАВЗУ: БИРИНЧИ ДАРАЖАЛИ БИР НОМАЪЛУМЛИ
ТАНҚОСЛАМАЛАРНИНГ ЭЧИМЛАРИ СОНИ ҲАҚИДАГИ ТЕОРЕМА.

1-ТАЪРИФ. Ушбу
ax b (modm) (1)
кўринишдаги таққослама бир номаълумли, биранчи даражали таққослама дейилади (бу ерда а ва b– бутун сонлар, m– натурал сон).
2-ТАЪРИФ.Aгap(1) таққосламада x=x1 бўлганда аx1b(mod m) такқослама тўғри бўлса, у ҳолда x1сон (1) таққосламани қаноатлантиради дейилади.
ТЕОРЕМА.Агар (1) таққосламани х1, сон қаноатлантирса, у ҳолда (1) таққосламани. x1+mt (t–бутун сон) сонлар системаси қаноатлантиради.
Ҳақиқатан, берилишнга кўра ax1b(mod m) таққослама тўғри.x1+mtсонлар системасига тегишли ихтиёрий x1сонни олайлик. У ҳолда x2=x1(modm) бўлиб, бундан 15-мавзудаги 5-хоссага кўра f(х2)f(х1)(modm)таққослама келиб чиқади. Бунда f(х1)f(х1)(modm)ни эътиборга олсак, f(х2)0(modm) таққосламага эга бўламиз, яъни х2 сон (1) таққосламани қаноатлантиради. Демак, х1+mtсонлар системасидаги ҳар бир сон (1) таққосламаниканоатлантирар экан.
x1+mtсонлар системаси ёки |x1|синф ҳам деб юритилади.
3-ТАЪРИФ.Aгap х1 сон (1) таққосламани қаноатлантирса, у ҳолда синф(1) таққосламанйнг ечами деб аталади.
(1) таққосламани қаноатлантирувчи совларни 0, 1, 2, . . .,m –1сонлар ичидан қидириш керак.
(1) таққосламани ечишнинг қуйидаги иккита ҳолини кўрайлик:
1. (а; m)=1бўлсин. Aгap (1) таққослама ечимга эга бўлса, бу ечим m модуль бўйича чегирмаларнинг бирор синфи бўлади. Маълумки, чегирмаларнинг тўла системасидаги ҳар бир чегирмага битта синф мос келар эди. Демак, (1) да х сон чегирмаларнинг тўла системасини қабул қилар экан. У ҳолда чизиқли форма ҳақидаги теоремага кўра ах ҳам чегирмаларнинг тўла системасини қабул қилади. х нинг бирор х0 қиймати топиладики, натижада ах0 чегирма билан b сон битта синфга тегишли бўлади, яъни ax0b (modm) бўлиб, xx0 (modm) бўлади. Бу ечим, юқорида айтилганидек, ёки [х0] кўринишларда ҳам белгиланади.
2.(а; m) = d>1бўлсин. (1) таққосламани унга тенг кучли ахb= ту (х,уZ) тенглик кўринишда ёзамиз. Бундан ax–my=b бўлиб, (а; m) =d га кўра a/dm/db/d. Демак, агар b d ҳолда, яъни b сон d га бўлинмаса, (1) такқослама ечимга эга бўлмайди.
Фараз қилайлик, b сон d га бўлинсин, яъни b= db1 бўлсин. Таққосламаларнинг хоссасига асосан (1) нинг иккала қисмини ва модулини d га бўлиб, қуйидагини ҳосил қиламиз:
a1xb1(mod т1).(2)
(2) таққослама (1) таққосламага тенг кучли эканлигини кўрсатамиз. –(2) таққосламанинг ихтиёрий ечими бўлсин. a1x1b1(modт1) таққосламанинг иккала қисмини ва модулини dгa кўпайтирамиз.
da1x1db1(mod т1)ax1b(mod m).
Демак, –(1)таққосламанинг ечими экан. –(1) таққосламанинг ихтиёрий ечими бўлсин. ax0b(mod m) таққосламанинг икала қисмини ва модулини d сонга бўламиз. У ҳолда a1x0b1(modт1) таққослама ҳосил бўлади, яьни –(2) таққосламанинг ечими экан. Демак, (1) ва(2) таққосламалар тенг кучли экан. (a1;m1) = 1 бўлганидан (1) ҳолга асосан (2) таққослама m1 модуль бўйича қуйидаги ягона ечимга эга: xх0(mod т1) ёки х=х0+m1k (kZ).Бy ечим (1) ни ҳам қаноатлантиради, лекин(1) нинг ечимлари шу билан тугамайди. Берилган таққосламанинг ечимларини m модуль бўйича топиш учун қуйидагиларга эътибор берамиз:
х1,x1+m1,..., х1+ (d1) т1 (3)
чегирмаларнинг ҳар бири m, модуль бўйича тенг қолдиқлар бўлиб. m1d=m модуль бўйича эса турли синфга тегишлидир. Шy турли синфларнинг элементлари
х1,x1+m1,x1+2m1,..., х1+ (d1) т1 (4)
дан иборат. Ҳақиқатан, (4) нинг ҳар қандай иккита элементи m модуль бўйича таққосланувчи эмас. (3) синфнинг (4) га кирмаган ҳар бир элементи учун (4) да шундай элемент топиладики, уларнинг айирмаси m1dтг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 бўлгани учун таққослама учта ечимга эга. Ҳақиқатан, таққосламани
2(mod5)
шаклида ёзиб оламиз, (3; 5) = 1 бўлгани учун бу таққослама 5 модуль бўйнча ягона x–1 (mod5) ечимга эга. У ҳолда берилган таққосламани –1, –1+5, –1+2∙5сонлар қаноатлантиради. Шунинг учун х–1, 4, 9 (mod 15) берилган таққосламанинг ечимлари бўлади.
23-МАВЗУ:БИРИНЧИ ДАРАЖАЛИ БИР НОМАЪЛУМЛИ ТАҚҚОСЛАМАЛАРНИ ЕЧИШ УСУЛЛАРИ
Ушбу
axb (modm) (1)
кўринишдаги бир номаълумли биринчи даражали таққосламаларни ечишнинг бир қанча усуллари мавжуд.
1. Синаш усули.Бу усулнинг моҳияти шундаки, (1) таққосламадаги х ўрнига m модулга кўра чегирмаларнинг тўла системасидаги барча чегирмалар кетма-кет қўйиб чиқилади. Улардан қайси бири( 1) ни тўғри таққосламага айлантирса, ўша чегирма қатнашган синф ечим ҳисобланади. Биз 22-мавзудаги иккита мисолни шу усулда ечдик. Лекин коэффициентлар етарлича ката бўлганда бу усул унча қулай бўлмайди.
2.Коэффициентларни ўзгартириш усули: Амалий машғулотларда тақкосламаларнинг хоссаларидан фойдаланиб, (1) да номаълум олдидаги коэффициентни ва bни шундай ўзгартириш керакки, натижада таққосламанинг ўнг томонида ҳосил бўлган сон ах ҳаднинг коэффициентига бўлинсин.
1-мисол. 7х 5 (mod9) таққосламани ечинг.
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,
32 9–2 (mod11), 344 (mod11),
33= 121(mod11)бўлганидан x= 39∙7= 286(mod11), х6(mod11)ечим ҳосил бўлади.
Таққосламанинг модули етарлича катта бўлса, қуйидаги усул анча фойдалидир.
4.Узлуксиз касрлардан фойдаланиш у с у л и.
Ушбу
ахb(mod m) (1)
таққослама берилган бўлиб, (а; m) = l ва а>0 бўлсин.
касрни узлуксиз касрга ёйиб, унинг муносиб касрларини каби белгилаймиз. қисқармас каср бўлганидан n= m, Qn бўлади, у ҳолда nQn-1 n-1Qn=(–1)n тенглик – Pn-1a=(–1)n шаклни олади. Охирги тенгликдан a Pn-1= – (–1)n +mQn-1 ёки a Pn-1 – (–1)n-1 (mod m) ҳосил бўлади. Охирги таққосламанинг иқкала қисмини (–1)n-1b ва кўпайтириб,
а(1)n-1bPn-1 b (modm) (2)
таққосламага эга бўламиз. (1) ва (2) ни солиштириб,
x (–l)n-1bPn-1 (modm) (3)
таққосламани ҳосил қиламиз. Бу ерда Pn-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
q1 = 3, q2 = 4, q3=7, q4 = 1, q5 = 2,
Қуйидаги жадвални тузамиз:



qk




3

4

7

1

2

Pk

1

3

13

94

107

308

Демак, Pn-1=P4= 107 экан. Бундан


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

Download 0.5 Mb.

Do'stlaringiz bilan baham:
  1   2   3   4   5   6   7




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling