Эҳтимоллик тестлари
Download 174.02 Kb.
|
Эҳтимоллик тестлари
- Bu sahifa navigatsiya:
- Сонни туб кўпайтувчиларга ажратиш Қуйидаги теорема туб кўпайтувчиларга ажратиш алгоритмини ифодалайди ҳамда берилган соннинг туб эканлигини аниқлаш имконини беради. Теорема
С аН (mod p), С = 3 4(mod 13) =3.
3u (mod 13) , 1 u 4 жадвал қийматларини ҳисоблаймиз: u =1, 3(mod 17) =3 u=2, 9(mod17) = 9 u=3, 27(mod 17)= 10 u=4, 81(mod17) = 3 7*3v(mod 13) , 0 v 4 жадвал қийматларини ҳисоблаймиз : v= 0, 7 (mod 13) = 7 v=1, 21(mod 17)=4 v=2, 21*3(mod 17) =12 v=3, 7*27(mod 17)= 2 v=4, 7*81(mod17)= 4 Иккита жадвал натижалари устма-уст тушган u, v –элементларни танлаб оламиз. Бироқ бундай қийматлар мавжуд эмас экан. Жавоб бутун ечим йўқ деган хулосага келамиз. Сонни туб кўпайтувчиларга ажратиш Қуйидаги теорема туб кўпайтувчиларга ажратиш алгоритмини ифодалайди ҳамда берилган соннинг туб эканлигини аниқлаш имконини беради. Теорема. Айтайлик, n >1 тоқ сон. Бу сон мураккаб сон бўлади фақат ва фақат p,q z+ булиб, n = p2 – q2 бўлса. Бу ерда p- q >1 . Ферма усулининг моҳияти шундан иборатки, теорема натижасига кўра p,q z+ сонлар топиш керакки, n = p 2 – q 2 ; p 2 = n+ q 2 ёки q 2 = n + p 2 бажарилсин. Агар p 2 = n+ q 2 , q =1,2,3……. қийматлар учун n+ q 2 -сон бирор соннинг тўла квадратидан иборат бўлмаса, у холда q = (n -1)/2 қиймат учун n+ q 2 -ни текшириб кўрамиз ва бирор соннинг квадратидан иборат бўлса. У ҳолда n – туб сон бўлади. Мисол. n =527 сони туб ёки туб эмаслиги аниқлансин.
Демак, q = 7 учун n+ q 2 =242 тўлиқ квадратидан иборат. Бу эса туб кўпайтувчиларга ёйилмаси бор дегани, яьни 527=242 -72 =(24-7)*(24+7) = 17*31. Натижа. Умуман олганда q =1,2,3……. (n -1)/2 =(527-1)/2 =263 қийматгача етиб бориши ҳар доим ҳам шарт эмас экан. Юқорида баён этилган усулни қуйидаги иккинчи тенглама кўринишда ҳам олиш мумкин эди, яьни q 2 = p 2 - n , р = m, m+1,.......... бу ерда m, сони сифатида қуйидаги m2 n шартни каноатлантирувчи энг кичик бутун сонни оламиз. Шу тартибда (p 2 - n) –сони, р = m, m+1,.......... қийматлар учун ҳисоблаймиз, токи (p 2 - n) –сон қандайдир соннинг тўлик квадрати бўлмагунча . Агар р= (n +1)/2 қийматгача (p 2 - n) –сон бирор соннинг тўлиқ квадратидан иборат бўлмаса, у ҳолда n – туб сон бўлади. Шуни алоҳида таькидлаш жоизки, бундай ҳолда текшириш юқориги ҳолдаги текширишимиздан камироқ микдордаги (сондаги) ҳисоблашларни талаб этади. Машқлар Ферма адгоритмидан фойдаланиб, қуйидаги сонларнинг туб ёки туб эмаслиги аниқлансин. Агар туб бўлмаса кўпайтувчиларга ёйилсин. 1001 1349 4851 1079 8051 567 7931 Download 174.02 Kb. Do'stlaringiz bilan baham: |
Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling
ma'muriyatiga murojaat qiling