Эҳтимоллик тестлари

С а^Н (mod p), С = 3 ⁴(mod 13) =3.

3^u (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

4. 
   7*3^v(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

5. 
   Иккита жадвал натижалари устма-уст тушган u, v –элементларни танлаб оламиз. Бироқ бундай қийматлар мавжуд эмас экан.
   
6. 
   Жавоб бутун ечим йўқ деган хулосага келамиз.
   

Сонни туб кўпайтувчиларга ажратиш
Қуйидаги теорема туб кўпайтувчиларга ажратиш алгоритмини ифодалайди ҳамда берилган соннинг туб эканлигини аниқлаш имконини беради.
Теорема. Айтайлик, n >1 тоқ сон. Бу сон мураккаб сон бўлади фақат ва фақат
p,q z⁺ булиб, n = p² – q² бўлса. Бу ерда p- q >1 .
Ферма усулининг моҳияти шундан иборатки, теорема натижасига кўра p,q z⁺ сонлар топиш керакки,
n = p ² – q ² ; p ² = n+ q ² ёки q ² = n + p ²
бажарилсин.
Агар p ² = n+ q ² , q =1,2,3…….
қийматлар учун n+ q ² -сон бирор соннинг тўла квадратидан иборат бўлмаса, у холда
q = (n -1)/2 қиймат учун n+ q ² -ни текшириб кўрамиз ва бирор соннинг квадратидан иборат бўлса. У ҳолда n – туб сон бўлади.
Мисол. n =527 сони туб ёки туб эмаслиги аниқлансин.

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

Демак, q = 7 учун
n+ q ² =24²
тўлиқ квадратидан иборат. Бу эса туб кўпайтувчиларга ёйилмаси бор дегани, яьни
527=24² -7² =(24-7)*(24+7) = 17*31.
Натижа. Умуман олганда
q =1,2,3……. (n -1)/2 =(527-1)/2 =263
қийматгача етиб бориши ҳар доим ҳам шарт эмас экан.
Юқорида баён этилган усулни қуйидаги иккинчи тенглама кўринишда ҳам олиш мумкин эди, яьни q ² = p ² - n , р = m, m+1,..........
бу ерда m, сони сифатида қуйидаги m² n шартни каноатлантирувчи энг кичик бутун сонни оламиз. Шу тартибда (p ² - n) –сони, р = m, m+1,..........
қийматлар учун ҳисоблаймиз, токи (p ² - n) –сон қандайдир соннинг тўлик квадрати бўлмагунча . Агар р= (n +1)/2 қийматгача (p ² - n) –сон бирор соннинг тўлиқ квадратидан иборат бўлмаса, у ҳолда n – туб сон бўлади.
Шуни алоҳида таькидлаш жоизки, бундай ҳолда текшириш юқориги ҳолдаги текширишимиздан камироқ микдордаги (сондаги) ҳисоблашларни талаб этади.


Машқлар
Ферма адгоритмидан фойдаланиб, қуйидаги сонларнинг туб ёки туб эмаслиги аниқлансин. Агар туб бўлмаса кўпайтувчиларга ёйилсин.

1. 
   1001
   
2. 
   1349
   
3. 
   4851
   
4. 
   1079
   
5. 
   8051
   
6. 
   567
   
7. 
   7931