2-ma’ruza Mavzu: Faktorlash muammosi va uni hisoblash; Qoldiq haqidagi Xitoy teoremasi; Sonni tub ko‘paytuvchilarga ajratish

Misol 6. Quyidagi
4x² – 11x -3 0 (mod 13)
kvadrat taqqoslama yechimini toping.
Yechish . 11 24 (mod 13) , 3 16 ( mod 13 ) , bo‘lgani uchun
4 x² - 24 x -16 0 (mod 13)
tenglik o‘rinli bo‘ladi. Taqqoslama xossasiga ko‘ra
EKUB( 4,13)=1
bo‘lganidan 4- ga qisqartirish mumkin, yani
x² – 6x – 4 0 ( mod 13) yoki ( x-3)² -13 0 (mod 13)
oxirgi taqqoslama ham (x-3)² 0 (mod 13) teng kuchli bo‘lib,
javob :
x 3 ( mod 13).
Tarif. Agar EKUB ( a, m) =1 bo‘lganda x² a ( mod m) taqqoslama yechimga ega bo‘lsa, a- ga m modul bo‘yicha kvadratik chegirma , aks holda a -ga m modul bo‘yicha kvadratik chegirmamas deyiladi.
Aytaylik, ushbu
x ² a ( mod r) , ( 5)
taqqoslama berilgan. Bu yerda EKUB (a, r) =1, EKUB( 2, r)=1 bo‘lib, r – tub son bo‘lsin. Bunday xususiyatdagi kvadratik chegirmalar uchun quyidagi tasdiq o‘rinli.
Tasdiq-1. (5) ko‘rinishdagi kvadratik chegirmada ( r-1 )/2 tasi kvadratik chegirma va yana shuncha sondagisi kvadratik chegirmamas bo‘ladi.
Tub modulli kvadratik taqqoslamalarni moduli yetarlicha kichik bo‘lganda quyidagi usul bo‘yicha hisoblash mumkin. Buning uchun r -modul bo‘yicha chegirmalarning keltirilgan sistemasidagi:
1, 2, 3,…… (r-1)/2
(xuddi shunday manfiy ishoralilarini ham yozilgan deb tushunish kerak) har bir chegirmani ketma-ket (5) ga qo‘yib o‘tirmasdan x- ni 1, 2,3,…. (r-1)/2 lar bilan almashtirish kifoya . Bunday xolda (5) ning chap tomonida
1² , 2², 3³ , …… , (( r-1 )/2)²
sonlar hosil bo‘ladi.
Misol 7. 11 modul bo‘yicha eng kichik musbat kvadratik chegirmalarni toping.
Yechish. Bizda r = 11 , u holda (11-1)/2 =5 bo‘lganidan , 1, 2,3,4,5 larning kvadratlarini qarab chiqamiz :
1² 1( mod 11), 2² 4 ( mod 11) , 3² 9( mod 11) , 4² 5( mod 11) ,
5² 3( mod 11) .
Demak, 11 modul buyicha kvadrat chegirmalar 1,4,9,5,3 lar bo‘lib; 2,6,7,8,10 lar kvadrat chegirmamaslar bo‘ladi.
Umuman quyidagi tasdiq o‘rinli: Agar (5) taqqoslama yechimga ega bo‘lsa, u holda yechim ikkita bo‘ladi.
Quyidagi Eyler kriteriyasi deb ataluvchi kriteriya esa (5) ko‘rinishdagi kvadrat taqqoslama yechimga ega yoki ega emasligini aniqlaydi.
Teorema (Eyler). Agar EKUB ( a, r)=1 bo‘lib ,
a ^{(r-1) / 2} 1 (mod p) o‘rinli bo‘lsa , (5) taqqoslama ikkita yechimga ega bo‘ladi, a ^{(r-1) / 2} -1 (mod p) o‘rinli bo‘lganda esa (5) taqqoslama birorta ham yechim yo‘q.
Lekin, bu kriteriyaning kamchilik tomoni shundaki, ushbu
x ² a (mod p) , EKUB (a, r) =1
taqqoslamada r – tub son yetarlicha katta bo‘lsa, bu taqqoslamani yechish masalasi murakkablashadi. Bunday xollarda L( a / r) ko‘rinishda belgilanuvchi va Lejandr simvoli deb ataluvchi quyidagicha simvoldan foydalaniladi.
Tarif. Quyidagi shartlarni qanoatlantiruvchi simvol:
1, agar a son r toq tub modul bo‘yicha kvadrat chegirma bo‘lsa;
L(a / r) =
-1, agar a son r toq tub modul bo‘yicha kvadrat chegirmamas bo‘lsa.
Lejandr simvoli deb ataladi. Bu yerda a soni Lejandr simvolining surati, r esa uning maxraji deyiladi. Shuningdek
L(a / r) = 0 , agar a 0 ( mod p) bo‘lsa,
u holda berilgan x ² 0 (mod p) taqqoslama ko‘rinishda bo‘lib, bu taqqoslamaning yechimi x 0 (mod p) bo‘ladi. Shu holda va faqat shu holdagina berilgan taqqoslama nol yechimga ega bo‘ladi.