TEOREMA - Muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari universiteti farg’ona filiali

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`cha chegirma qatnashgan sinf yechim hisoblanadi. Lekin koeffitsient yetarlicha katta bo`lganda bu usul qulay emas.
Koeffitsientlarni o`zgartirish usuli. Taqqoslamalarning xossalaridan foydalanib, (1) da no’ma`lum oldidagi koeffitsientni va b ni shunday o`zgartirish kerakki, natijada taqqoslamaning o`ng tomonida hosil bo`lgan son 𝑎𝑥 hadning koeffitsientiga bo`linsin.
MISOL. 1. 7𝑥 ≡ 5(𝑚𝑜𝑑9) 7𝑥 ≡ 5 + 9(𝑚𝑜𝑑9)
7𝑥 ≡ 14(𝑚𝑜𝑑9)
𝑥 ≡ 2(𝑚𝑜𝑑9)
2. 17𝑥 ≡ 25(𝑚𝑜𝑑28)
17𝑥 + 28𝑥 ≡ 25(𝑚𝑜𝑑28)
45𝑥 ≡ 25(𝑚𝑜𝑑28)
9𝑥 ≡ 5(𝑚𝑜𝑑28)
9𝑥 ≡ 5 − 140(𝑚𝑜𝑑28)
9𝑥 ≡ −135(𝑚𝑜𝑑28)
𝑥 ≡ −15(𝑚𝑜𝑑28)
𝑥 ≡ 13(𝑚𝑜𝑑28)
Eyler teoremasidan foydalanish usuli. Ma`lumki, (𝑎, 𝑚) = 1 bo`lsa, u holda 𝑎𝜑(𝑚) ≡ 1 (𝑚𝑜𝑑𝑚) taqqoslama o`rinli edi. Shunga ko`ra, 𝑥 = 𝑎𝜑(𝑚)−1 ∙
𝑏(𝑚𝑜𝑑𝑚) bo`ladi.
Misol. 3𝑥 ≡ 7(𝑚𝑜𝑑11)
𝑥 ≡ 3𝜑(11)−1 ∙ 7(𝑚𝑜𝑑11) 𝜑(11) = 10
𝑥 ≡ 39 ∙ 7(𝑚𝑜𝑑11) ≡ (33)3 ∙ 7 ≡ 53 ∙ 7 ≡ 4 ∙ 7 ≡
28 ≡ 6(𝑚𝑜𝑑11)
Taqqoslamaning moduli yetarlicha katta bo`lsa, quidagi usul ancha qulaydir.
Uzluksiz kasrlardan foydalanish usuli.
𝑎𝑥 ≡ 𝑏(𝑚𝑜𝑑𝑚)
taqqoslama berilgan bo`lib, (𝑎, 𝑚) = 1 ∧ 𝑎 > 0 bo`lsin. 𝑚
𝑎
kasrni uzluksiz
kasrlarga yoyib, uning munosib kasrlarini 𝑃𝑘
𝑄𝑘
(𝑘 = ̅1̅̅,̅𝑛̅) kabi belgilaymiz, bunda
𝑃𝑛 = 𝑚 ∧ 𝑄𝑛 = 𝑎 bo`ladi, u holda
𝑃𝑛𝑄𝑛−1 − 𝑃𝑛−1𝑄𝑛 = (−1)𝑛
tenglikni
𝑚𝑄𝑛−1 − 𝑎𝑃𝑛−1 = (−1)𝑛
ko`rinishda yozish mumkin, yoki
𝑎𝑃 𝑛−1 ≡ (−1 )𝑛 + 𝑚𝑄 𝑛−1 dan
𝑎𝑃 𝑛−1 ≡ (−1 )𝑛−1(𝑚𝑜𝑑𝑚 ) (2)
(2) ni (−1) 𝑛−1 ∙ 𝑏 ga ko`paytirib,
(−1) 𝑛−1 ∙ 𝑏 ∙ 𝑎𝑃 𝑛−1 ≡ 𝑏(𝑚𝑜𝑑𝑚) (3)
va (3) ni solishtirib
𝑥 ≡ (−1 )𝑛−1𝑏 ∙ 𝑃 𝑛−1(𝑚𝑜𝑑𝑚)
ni hosil qilamiz. Bu erda 𝑃𝑛−1
son 𝑚
𝑎
kasrning (𝑛 − 1) − munosib kasrning
suratidan iborat.
taqqoslama yagona yechimga ega bo`lgani uchun (3) yechim (1) ning yagona yechimi bo`ladi.
MISOL. 68𝑥 ≡ 164(𝑚𝑜𝑑212)
(68,164 ) = 4, 212/4
17𝑥 ≡ 41 (𝑚𝑜𝑑53 ), (17,53 ) = 1
𝑃 𝑘−1 = 25 𝑛 = 3, 𝑛 − 1 = 2
𝑥 0 ≡ (−1 )2 ∙ 25 ∙ 41 (𝑚𝑜𝑑53 ) ≡ 18 (𝑚𝑜𝑑53 )
𝑥 ≡ 18, 71, 124, 177(𝑚𝑜𝑑212)
Ljandr simvoli va uning xossalari.
Ushbu 𝑥2 ≡ 𝑎 (𝑚𝑜𝑑 𝑝) , (𝑎; 𝑝) = −1 taqqoslamaning moduli yetarlicha katta bo’lganda Eyler kriteriysidan foydalaninsh unchalik qulay emas. Bunda
)
(
hollarda Lejandr simvoli deb ataluvchi va 𝑎
𝑝
foydalaniladi.
Ta’rif. Quyidagi shatrlarniqanoatlantiruvchi deyiladi:
𝑎
kabi atluvchi simvoldan
)
(
𝑎 simvol Lejandr simvoli
𝑝
( )
𝑝
1, 𝑎𝑔𝑎𝑟 𝑎 𝑠𝑜𝑛 𝑝 𝑡𝑜𝑞 𝑡𝑢𝑏 𝑚𝑜𝑑𝑢𝑙 𝑏𝑜′𝑦𝑖𝑐ℎ𝑎𝑘𝑣𝑎𝑑𝑟𝑎𝑡𝑖𝑘 𝑐ℎ𝑒𝑔𝑖𝑟𝑚𝑎 𝑏𝑜′𝑙𝑠𝑎;
= {−1, 𝑎𝑔𝑎𝑟 𝑎 𝑠𝑜𝑛 𝑝 𝑡𝑜𝑞 𝑡𝑢𝑏 𝑚𝑜𝑑𝑢𝑙 𝑏𝑜′𝑦𝑖𝑐ℎ𝑎𝑘𝑣𝑎𝑑𝑟𝑎𝑡𝑖𝑘 𝑐ℎ𝑒𝑔𝑖𝑟𝑚𝑎𝑚𝑎𝑠 𝑏𝑜′𝑙𝑠𝑎.
)
(
𝑎 simvol a sondan p bo’yicha tuzlgan Lejandr simvoli deb taladi, bu yerda a
𝑝
Lejandr simbolining surati, p esa Lejandr simvolining maxraji deyiladi.
Misol. (
7 ) = 𝟏, chunki Eyler kriteriysiga asosan, 7
19
19−1
2 ≡ 1 (𝑚𝑜𝑑 19)
bo’lgani uchun 7 son 19 modul bo’yicha vadratik chegirmadir. 5 son 17 modul
bo’yicha kvadratik chegirmamas bo’lganligidan
( 5 )
= −1 bo’ladi.
17
Ma’lumki, 𝑎
𝑝−1
2 ≡ 1 (𝑚𝑜𝑑 𝑝) , 𝑎
𝑝−1
2 ≡ −1 (𝑚𝑜𝑑 𝑝) ekanligiga qarab, a
kvadratik chegirma yoki kvadratik chegirmamas bo’ladi. Demak, Ljandr simvoli va Eyler kriteriylariga asosan, quyidagini yoza olamiz:
(
𝑎) ≡ 𝑎
𝑝
𝑝−1
2 (𝑚𝑜𝑑 𝑝). (1)
Endi Lejandr simvolining quyidagi ba’zi bir xossalarini o’rib chiqamiz:
1-xossa. 𝑎 ≡ 𝑎1
(𝑚𝑜𝑑 𝑝) => 𝑎
)
(
𝑝
= 𝑎 )
1
(
𝑝
. (2)
Haqiqatan, bitta sinfning elementlari berilgan modul bo’yicha yo kvadratik chegirma, yoki kvadratik chegirmamas bo’ladi. Bunga asosan, (1) ning to’g’rilii kelib chiqadi. Bu xossadan foydalanib, har qanday 𝑘 ∈ 𝑍 uhun quyidagini yoza
(
olamiz: (𝑎) = (𝑘𝑝+𝑎1), (𝑘𝑝+𝑎1) = 𝑎
) bo’lgani uchun 𝑎 = (𝑎1)
bo’ladi.
1
)
(
𝑝 𝑝 𝑝 𝑝
2-xossa. (1) = 1 .
𝑝 𝑝
𝑝
Haqiqatan, 𝑥2 ≡ 1 (𝑚𝑜𝑑 𝑝) taqqoslama doimo yechimga ega bo’lib, 𝑥 ≡
±1 (𝑚𝑜𝑑 𝑝) uning yehimidir.
(
xossa. −1
𝑝
) = (−1)
𝑝−1
2 .
(1) taqqoslamaga asosan quyidagini yoza olamiz:
−1 𝑝−1
( ) = (−1)
𝑝
2 (𝑚𝑜𝑑 𝑝) (3).
−1 𝑝−1
Lekin (
𝑝
) va (−1)
2 larning qiymati ±1 dan farqli emas. Shu bilan bir
vaqtda p toq tub son bo’lgani uchun 1 va -1 lar shu modul bo’yicha taqqoslanuvchi
−1 𝑝−1
bo’la olmaydi. Demak, (
𝑝
bo’ladi.
) va (−1)
2 lar bir vaqtda 1 ga yoki -1 ga teng
xossa. (𝑎∙𝑏) ≡
𝑝
𝑎 𝑏
)
∙
.
( ( )
𝑝 𝑝
Isboti. (1) taqqoslaamaga asosan quyidagini yozish mumkin: (𝑎∙𝑏) ≡
𝑝
𝑝−1
𝑝−1
𝑝−1
𝑎 𝑏
𝑎∙𝑏 𝑎
(𝑎 ∙ 𝑏)
𝑏
2 ≡ (𝑎)
2 ∙ (𝑏)
𝑝−1
2 ≡ (
𝑝
𝑝−1
) ∙ (
𝑝
𝑎
) (𝑚𝑜𝑑 𝑝) yoki (
𝑝
𝑏
) ≡ ( ) ∙
𝑝
( ) (𝑚𝑜𝑑 𝑝) . (𝑎)
𝑝
2 ∙ (𝑏)
2 ≡ (
𝑝
) ∙ (
𝑝
) (𝑚𝑜𝑑 𝑝) taqqoslamaning ikkala qismi
a va b lar p modul bo’yicha kvadratik chegirma yoki kvadratik chegirmamas bo’lsa, 1 ga, a va b larning biri p modul bo’yicha kvadratik chegirma, ikkinchisi
esa kvadratik chegirmamas bo’lsa, -1 ga teng. Shuning uchun ( 𝑎∙𝑏) ≡
𝑝
tenglikni yosa olamiz. Bu xossadan quyidagi natijalar kelib chiqadi:
( 𝑎)
𝑝
𝑝
)
.
(
1-natija. (𝑎2) ≡ 1, (𝑎∙𝑏2) ≡ 𝑎
𝑝 𝑝 𝑝
2-natija. Juft sondagi kvadratik chegirmalar yoki kvadratik chegirmamaslar ko’paytmasi doimo kvadratik chegirma bo’ladi. Toq sondagi kvadratik chegirmamaslar ko’paytmasi yana kvadratik chegirmamas bo’ladi.
2 𝑝2−1
Biz bu xossani isbot qilib o’tirmasdan undan amaliy mashg’ulotlarda foydalnishning a’zi bir tomonlarin ko’rsatib o’tamiz.
𝑝 ≡ 8𝑚 ± 1 shakldagi tub son bo’lsin. U holda
𝑝2 − 1
=
8
(8𝑚 ± 1)2 − 1
8
= 8𝑚2 ± 2𝑚 ≡ 0 (𝑚𝑜𝑑 2)
Bo’lgani uchun ( 2) ≡ 1.
𝑝
𝑝 ≡ 8𝑚 ± 3 shakldagi tub son bo’lsa,
𝑝2 − 1
=
8
(8𝑚 ± 3)2 − 1
8
= 8𝑚2 ± 6𝑚 + 1 ≡ 1 (𝑚𝑜𝑑 2)
bo’adi. Demak, 𝑝 ≡ 8𝑚 ± 3 shakldagi tub son bo’lsa, 2 son p modul boyicha
kvadratik chegirmamas bo’lad, ya’ni (2)
≡ −1.
𝑝
xossa. O’zarolik qonuni.
Agar p va q lar har xil toq tub son bo’lsa,
𝑝 𝑞
𝑝−1∙𝚐−1
tenglik o’rinli bo’ladi.
( ) ∙ (
𝑞 𝑝
) ≡ (−1) 2 2 (4)
Bu xossani ham isbot qilmasan uning amaliy mashg’ulotlardaqo’llanishini
ko’rsatmiz. Buning uchun (4) ning har ikkaa qismini
(𝑝)
𝑞
ga ko’paytiramiz:
𝑞 𝑝−1 𝚐−1 𝑝
bu yerda
2
𝑝) = 1.
(
𝑞
( ) ≡ (−1) 2 ∙
𝑝
2 ( ), (5)
𝑞
(5) tenglikka asosan, p va q larning kamida bittasi 4m+1 shakldagi son bo’lsa,
𝑝−1 𝚐−1
𝑝 𝑞
(−1)
2 ∙ 2 = 1 bo’lib, (
𝑞
) = (
𝑝
) hosil boladi.
Agar p va q larning har biri 4m+3 shaklagi tub son bo’lsa,u holda (-1) ning
darajasi toq son bo’lib,
(𝑝)
𝑞
𝑞
= − ( )
𝑝
bo’ladi.
Misol. 𝑥2 ≡ 426(𝑚𝑜𝑑 491) taqqoslama yechimga egami?
Bu savolga javob berish uchun (426) Lejandr simvolini tuzamiz. 426 = 2 ∙
491
3 ∙ 71 shakldagi son bo’lgani uchun 4- xossaga asosan quyidagicha yozamiz:
( ) (
(426) ≡ 2 ∙ 3
) ∙ ( 71 ) .
491
491
491
491
( 2 ) ≡ −1, chunki 491 ≡ 3 (𝑚𝑜𝑑 8).
491
(
)
( 3 ) ≡ − (491) ≡ − 2
≡ − (−1 ) = 1, chunki 491 ≡ 3 (𝑚𝑜𝑑 4) va 3 ≡
491 3 3
)
(
)
(
)
(
)
(
)
(
)
3 (𝑚𝑜𝑑 4) hamda 3 ≡ 3 (𝑚𝑜𝑑 8).
(
)
(
( 71 ) ≡ − (491) ≡ − 65 ≡ − 5
≡ − 71
≡ − 1 ∙ 6 ≡
491
71 71
71 71
5 13
5 13
)
(
)
(
− ( 2 ) ∙ ( 3 ) ≡ −(−1) 13 ≡ 1 ∙ 1
≡ 1, chunki 491 ≡ 3(𝑚𝑜𝑑 4), 71 ≡
13 13 3 3
3 (𝑚𝑜𝑑 4), 491 ≡ 65 (𝑚𝑜𝑑 71), 5 ≡ 1 (𝑚𝑜𝑑 4), 13 ≡ 5 (𝑚𝑜𝑑 8).
Demak, (426) ≡ (−1) ∙ 1 ∙ 1 = −1, (426) ≡ −1 , bo’lgan uchun berilgan
491
taqqoslama yechimga ega emas.
|