Matematika-informatika kafedrasi

5-§ 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 ( 𝑝 ) kabi atluvchi simvoldan foydalaniladi. Ta’rif. Quyidagi shatrlarniqanoatlantiruvchi ( 𝑝 ) simvol Lejandr simvoli deyiladi: ( 𝑎 𝑝 ) = { 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 19) = 𝟏, chunki Eyler kriteriysiga asosan, 7 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 17) = −1 bo’ladi. 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 𝑝 ) = ( 𝑎1 𝑝 ) bo’lgani uchun ( 𝑎 𝑝 ) = ( 𝑎1 𝑝 ) bo’ladi. 2-xossa. ( 1 𝑝 ) = 1 . Haqiqatan, 𝑥 2 ≡ 1 (𝑚𝑜𝑑 𝑝) taqqoslama doimo yechimga ega bo’lib, 𝑥 ≡ ±1 (𝑚𝑜𝑑 𝑝) uning yehimidir. 3-xossa. ( −1 𝑝 ) = (−1) 𝑝−1 2 . (1) taqqoslamaga asosan quyidagini yoza olamiz: ( −1 𝑝 ) = (−1) 𝑝−1 2 (𝑚𝑜𝑑 𝑝) (3). Lekin ( −1 𝑝 ) va (−1) 𝑝−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 bo’la olmaydi. Demak, ( −1 𝑝 ) va (−1) 𝑝−1 2 lar bir vaqtda 1 ga yoki -1 ga teng bo’ladi. 4-xossa. ( 𝑎∙𝑏 𝑝 ) ≡ ( 𝑎 𝑝 ) ∙ ( 𝑏 𝑝 ) . Isboti. (1) taqqoslaamaga asosan quyidagini yozish mumkin: ( 𝑎∙𝑏 𝑝 ) ≡ (𝑎 ∙ 𝑏) 𝑝−1 2 ≡ (𝑎) 𝑝−1 2 ∙ (𝑏) 𝑝−1 2 ≡ ( 𝑎 𝑝 ) ∙ ( 𝑏 𝑝 ) (𝑚𝑜𝑑 𝑝) yoki ( 𝑎∙𝑏 𝑝 ) ≡ ( 𝑎 𝑝 ) ∙ ( 𝑏 𝑝 ) (𝑚𝑜𝑑 𝑝) . (𝑎) 𝑝−1 2 ∙ (𝑏) 𝑝−1 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. 5-xossa. ( 2 𝑝 ) ≡ (−1) 𝑝 2−1 8 . Biz bu xossani isbot qilib o’tirmasdan undan amaliy mashg’ulotlarda foydalnishning a’zi bir tomonlarin ko’rsatib o’tamiz. a) 𝑝 ≡ 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. b) 𝑝 ≡ 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. 6-xossa. O’zarolik qonuni. Agar p va q lar har xil toq tub son bo’lsa, ( 𝑞 ) ∙ ( 𝑞 𝑝 ) ≡ (−1) 𝑝−1 2 ∙ 𝑞−1 2 (4) tenglik o’rinli bo’ladi. Bu xossani ham isbot qilmasan uning amaliy mashg’ulotlardaqo’llanishini ko’rsatmiz. Buning uchun (4) ning har ikkaa qismini ( 𝑞 ) ga ko’paytiramiz: ( 𝑞 𝑝 ) ≡ (−1) 𝑝−1 2 ∙ 𝑞−1 2 ( 𝑝 𝑞 ), (5) bu yerda ( 𝑝 𝑞 ) 2 = 1. (5) tenglikka asosan, p va q larning kamida bittasi 4m+1 shakldagi son bo’lsa, (−1) 𝑝−1 2 ∙ 𝑞−1 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 491) Lejandr simvolini tuzamiz. 426 = 2 ∙ 3 ∙ 71 shakldagi son bo’lgani uchun 4- xossaga asosan quyidagicha yozamiz: ( 426 491) ≡ ( 2 491) ∙ ( 3 491) ∙ ( 71 491) . 1. ( 2 491) ≡ −1, chunki 491 ≡ 3 (𝑚𝑜𝑑 8). 2. ( 3 491) ≡ − ( 491 3 ) ≡ − ( 2 3 ) ≡ −(−1) = 1, chunki 491 ≡ 3 (𝑚𝑜𝑑 4) va 3 ≡ 3 (𝑚𝑜𝑑 4) hamda 3 ≡ 3 (𝑚𝑜𝑑 8). 3. ( 71 491) ≡ − ( 491 71 ) ≡ − ( 65 71) ≡ − ( 5 71) ∙ ( 13 71) ≡ − ( 71 5 ) ∙ ( 71 13) ≡ − ( 1 5 ) ∙ ( 6 13) ≡ − ( 2 13) ∙ ( 3 13) ≡ −(−1) ( 13 3 ) ≡ 1 ∙ ( 1 3 ) ≡ 1, chunki 491 ≡ 3(𝑚𝑜𝑑 4), 71 ≡ 3 (𝑚𝑜𝑑 4), 491 ≡ 65 (𝑚𝑜𝑑 71), 5 ≡ 1 (𝑚𝑜𝑑 4), 13 ≡ 5 (𝑚𝑜𝑑 8). Demak, ( 426 491) ≡ (−1) ∙ 1 ∙ 1 = −1, ( 426 491) ≡ −1 , bo’lgan uchun berilgan taqqoslama yechimga ega emas.