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

2-kadam. r_m = a (mod n) qiymatni yuklaymiz.
3-kadam. Barcha k = m-1, m-2, …..2,1 va k = 0 qiymatlar uchun

r_k+1² (mod n), agar v_k =0 bo‘lsa

r_k =
r_k+1² a (mod n), agar v_k =1 bo‘lsa.
4-kadam . 3-qadamning oxirgi natijasi r₀ = aye (mod n) biz qidirayotgan yechim deb elon qilinadi.
Misol-1. 43¹⁰³² (mod 41) – qoldiqni hisoblang.
Yechish: e=1032, bu sonni ikkilik sanoq sistemasiga o‘tkazamiz:
1032= 2¹⁰ +2³ = 10000001000₂
yani m=10 , (v₁₀ v₉ v₈ v₇ v₆ v₅ v₄ v₃ v₂ v₁v₀ ) ₂ = (10000001000)₂
Demak, algoritm qadamiga muvofiq:
R_m , m =10,9,…1,0
Qiymatlar quyidagi qoida bo‘yicha hisoblanadi:
R₁₀ = 43 (mod 41)=2,
R₉ = 2² *(mod 41)= 4,
R₈ = 4²(mod 41)=16,
R₇ =16²(mod 41)=10,
R₆ = 10² (mod 41)=18,
R₅ = 18² (mod 41)= 37,
R₄ =37²(mod 41)= 16,
R₃ =16² *43(mod 41)= 20
R₂=20² (mod 41)=31,
R₁= 31²(mod 41)=18,
R₀ = 18² (mod 41)=37.
javob
43¹⁰³² (mod 41) = 37.
Mashqlar
Effektiv algoritm yordamida quyidagilar hisoblansin.
№1 3²⁷⁵ (mod 100).
№2 6⁵⁰⁰⁰ ( mod 1000).
№3 11²⁴⁶⁸¹ ( mod 83).
Kvadratik taqqoslama
Tarif. Ushbu
ax² + b x + c 0 ( mod m), (1)
ko‘rinishdagi taqqoslama kvadratik taqqoslama deyiladi.
Bu yerda a soni m ga bo‘linmaydi.
Teorema. (1) ko‘rinishdagi kvadratik taqqoslamani har doim

x ² d ( mod m₁ ) (2)

ko‘rinishga keltirsh mumkin.
Haqiqatan , (1) ning ikkala qismini va va modulini 4*a ga ko‘paytirsak ( bunga haqqimiz bor, chunki taqqoslama xossasiga ko‘ra ):
4a² x² + 4 a b x + 4as 0 ( mod 4m*a)
yoki
(2ax +b) ² – b² + 4ac 0 ( mod 4m*a) ,
u = 2ax + b desak, oxirgi taqqoslama
u² b² – 4ac ( mod 4 m*a) (3)
ko‘rinishga keladi . Nixoyat b² – 4ac = d , 4*m*a = m₁ belgilash kiritib,
u² d ( mod m₁ ) (4)
taqqoslamani hosil qilamiz. (1) ning har bir yechimi (4) ni ham qanoatlantiradi. Lekin (4) har bir yechimi (1) ning ham yechimi bo‘lavermaydi. Shuning uchun (4) ning yechimlari orasidan (1) ning ham yechimi bo‘ladiganlarini ajrata olish kerak . Buning uchun esa
x = (u-b)/ 2a
nisbat butun son ekanligiga qarash kerak, yani nisbat butun son bo‘lsa , (4) qanoatlantiruvchi yechim (1) ning ham yechimi bo‘ladi. Odatda misollar yechishda (1) dan (4) ga o‘tishda, taqqoslamaning chap qismini biror ifodaning to‘la kvadrati shakliga keltirib olish lozim.
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.
Misol 7. Quyidagi
x ² 7 ( mod 19)
taqqoslama yechimi bor yoki yo‘qligi ko‘rsatilsin.
Yechish. Bizda a =7, r =19 , EKUB (7, 19) =1 bo‘lib, Eyler kriteriyasiga ko‘ra :

5. 
   
   ^{(19-1) / 2} 1 ( mod 19)
   

bo‘lgani uchun 7 son 19 modul bo‘yicha kvadratik chegirmadir, yani

L( 7/ 19) =1 .