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


Download 72.77 Kb.
bet1/7
Sana03.12.2023
Hajmi72.77 Kb.
#1797942
  1   2   3   4   5   6   7
Bog'liq
2-ma’ruza Mavzu Faktorlash muammosi va uni hisoblash; Qoldiq ha-www.fayllar.org



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 = p2 – q2 bo‘lsa. Bu yerda p- q >1 .
Ferma usulining mohiyati shundan iboratki, teorema natijasiga ko‘ra p,q z+ sonlar topish kerakki,
n = p 2 – q 2 ; p 2 = n+ q 2 yoki q 2 = n + p 2
bajarilsin.
Agar p 2 = n+ q 2 , q =1,2,3…….
qiymatlar uchun n+ q 2 -son biror sonning to‘la kvadratidan iborat bo‘lmasa, u xolda
q = (n -1)/2 qiymat uchun n+ q 2 -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=242

Demak, q = 7 uchun


n+ q 2 =242
to‘liq kvadratidan iborat. Bu esa tub ko‘paytuvchilarga yoyilmasi bor degani, yani
527=242 -72 =(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 2 = p 2 - n , r = m, m+1,..........
bu yerda m, soni sifatida quyidagi m2 n shartni kanoatlantiruvchi eng kichik butun sonni olamiz. Shu tartibda (p 2 - n) –soni, r = m, m+1,..........
qiymatlar uchun hisoblaymiz, toki (p 2 - n) –son qandaydir sonning to‘lik kvadrati bo‘lmaguncha . Agar r= (n +1)/2 qiymatgacha (p 2 - 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.



Download 72.77 Kb.

Do'stlaringiz bilan baham:
  1   2   3   4   5   6   7




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling