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

2-ma’ruza
Mavzu: Faktorlash muammosi va uni hisoblash; Qoldiq haqidagi Xitoy teoremasi;
Sonni tub ko‘paytuvchilarga ajratish
Quyidagi teorema tub ko‘paytuvchilarga ajratish algoritmini ifodalaydi hamda berilgan sonning tub ekanligini aniqlash imkonini beradi.
Teorema. Aytaylik, n >1 toq son. Bu son murakkab son bo‘ladi faqat va faqat
p,q z⁺ bulib, n = p² – q² bo‘lsa. Bu yerda p- q >1 .
Ferma usulining mohiyati shundan iboratki, teorema natijasiga ko‘ra p,q z⁺ sonlar topish kerakki,
n = p ² – q ² ; p ² = n+ q ² yoki q ² = n + p ²
bajarilsin.
Agar p ² = n+ q ² , q =1,2,3…….
qiymatlar uchun n+ q ² -son biror sonning to‘la kvadratidan iborat bo‘lmasa, u xolda
q = (n -1)/2 qiymat uchun n+ q ² -ni tekshirib ko‘ramiz va biror sonning kvadratidan iborat bo‘lsa. U holda n – tub son bo‘ladi.
Misol. n =527 soni tub yoki tub emasligi aniqlansin.

q	n+ q ^2
1	527+1=528
2	527+4=531
3	527+9=536
4	527+16=543
5	627+25=552
6	527+36=563
7	527+49=576=24^2

Demak, q = 7 uchun

n+ q ² =24²
to‘liq kvadratidan iborat. Bu esa tub ko‘paytuvchilarga yoyilmasi bor degani, yani
527=24² -7² =(24-7)*(24+7) = 17*31.
Natija. Umuman olganda
q =1,2,3……. (n -1)/2 =(527-1)/2 =263
qiymatgacha yetib borishi har doim ham shart emas ekan.
Yuqorida bayon etilgan usulni quyidagi ikkinchi tenglama ko‘rinishda ham olish mumkin edi, yani q ² = p ² - n , r = m, m+1,..........
bu yerda m, soni sifatida quyidagi m² n shartni kanoatlantiruvchi eng kichik butun sonni olamiz. Shu tartibda (p ² - n) –soni, r = m, m+1,..........
qiymatlar uchun hisoblaymiz, toki (p ² - n) –son qandaydir sonning to‘lik kvadrati bo‘lmaguncha . Agar r= (n +1)/2 qiymatgacha (p ² - n) –son biror sonning to‘liq kvadratidan iborat bo‘lmasa, u holda n – tub son bo‘ladi.
Shuni alohida takidlash joizki, bunday holda tekshirish yuqorigi holdagi tekshirishimizdan kamiroq mikdordagi (sondagi) hisoblashlarni talab etadi.