Պարզ թիւ

Պարզ թիւ, մէկէն մեծ բնական թիւ մը, որ երկու աւելի փոքր բնական թիւերու արտադրեալը չէ։ Մէկէն մեծ այն բնական թիւը, որ պարզ չէ, կը կոչուի բաղադրեալ թիւ։ Օրինակ՝ 5-ը պարզ թիւ է, որովհետեւ կարելի է զայն ներկայացնել միայն 1 \times 5 եւ 5 \times 1 արտադրեալներու տեսքով։ Սակայն 4-ը բաղադրեալ է, քանի որ կարելի է զայն ներկայացնել 2 \times 2 տեսքով։ Թուաբանութեան հիմնական թէորեմին պատճառով, պարզ թիւերը հիմնարար դեր ունին թիւերու տեսութեան մէջ։ Ըստ թէորեմին՝ մէկէն մեծ իւրաքանչիւր n բնական թիւ կամ պարզ է, կամ ալ կը վերլուծուի պարզ թիւերու արտադրեալի՝ այն ալ միակ ձեւով։ Այսինքն, եթէ $n = p_1 p_2 \dots p_k, ուր p_1, p_2, \dots, p_k թիւերէն իւրաքանչիւրը պարզ թիւ է, եւ եթէ անոնք դասաւորուած են ըստ աճման կարգի (p_1 \le p_2 \le \dots \le p_k$), ապա այդ վերլուծումը միակն է։

Տրուած n թիւի մը պարզութիւնը ստուգելու համար կարելի է հերթով փորձել եւ տեսնել, թէ արդեօք n-ը կը բաժնուի՞ 2-ի եւ n-ի միջեւ գտնուող որեւէ ամբողջ թիւի։ Այս ալկորիթմը պարզ է, բայց դանդաղ։ Աւելի արագ ալկորիթմներէն են՝ Միլըր-Ռապինի (Miller–Rabin) պարզութեան փորձը, որ արագ է, բայց սխալելու փոքր հաւանականութիւն մը ունի, եւ AKS պարզութեան փորձը, որ միշտ բազմանդամային արագութեամբ կը գտնէ ճիշդ պատասխանը, բայց գործնականին մէջ չափազանց դանդաղ է կիրարկուելու համար։ Յատուկ տեսքի թիւերու համար, ինչպէս օրինակ Մերսէնի (Mersenne) թիւերը, գոյութիւն ունին աւելի արագ մեթոտներ։ Դեկտեմբեր 2018-ի տուեալներով՝ մեծագոյն ծանօթ պարզ թիւը Մերսէնի թիւ մըն է, որ ունի 24,862,048 թուանշան։

Պարզ թիւերը անվերջ են։ Ասոր ճշմարտացիութեան առաջին ապացոյցը կը հանդիպինք Էվկլիտեսի մօտ։ Անոր ապացոյցը կարելի է համառօտ ձեւակերպել այսպէս․

Ենթադրենք, թէ պարզ թիւերու քանակը վերջաւոր է։ Բոլոր պարզ թիւերը բազմապատկենք իրարով եւ ստացուած արտադրեալին գումարենք մէկ։ Ստացուած նոր թիւը չի բաժնուիր մեր ունեցած պարզ թիւերէն ոչ մէկուն վրայ, որովհետեւ բաժանումէն մնացորդը միշտ մէկ կ’ըլլայ։ Հետեւաբար, այդ թիւը պէտք է բաժնուի նոր պարզ թիւի մը վրայ, որ մենք չէինք ներառած մեր ցուցակին մէջ։ Այսպիսով կը յանգինք հակասութեան։

Պարզ թիւերը բաղադրեալ թիւերէն զատող որեւէ ծանօթ բանաձեւ չկայ։ Սակայն, բնական թիւերուն մէջ պարզ թիւերու բաշխումը կարելի է վիճակագրական ձեւով մոտելաւորել։ Այս ուղղութեամբ առաջին արդիւնքը Պարզ թիւերու թէորեմն էր, որ ապացուցուեցաւ 19-րդ դարու վերջաւորութեան։ Ըստ այս թէորեմին՝ հաւանականութիւնը, որ պատահականօրէն ընտրուած մեծ թիւ մը պարզ ըլլայ, հակադարձ համեմատական է իր թուանշաններու քանակին, այսինքն՝ իր լոկարիթմին։

Պարզ թիւերու հետ կապուած որոշ խնդիրներ տակաւին մնացած են չլուծուած։ Այս խնդիրներէն են՝ Կոլտպախի (Goldbach) խնդիրը (երկուքէն մեծ իւրաքանչիւր զոյգ ամբողջ թիւ կարելի է ներկայացնել երկու պարզ թիւերու գումարի տեսքով) եւ երկուորեակ պարզ թիւերու վարկածը (գոյութիւն ունին անթիւ բազմութեամբ պարզ թիւերու զոյգեր, որոնք իրարմէ միայն երկու միաւորով տարբեր են)։ Նման հարցեր խթանած են թիւերու տեսութեան տարբեր բնագաւառներու զարգացումը, ինչպէս օրինակ՝ վերլուծական (analytic) կամ հանրահաշուական թիւերու տեսութիւնը։ Պարզ թիւերը նաեւ լայն կիրառութիւն ունին տեղեկատուական արհեստագիտութեան, մասնաւորապէս՝ հանրային բանալիներու գաղտնագրութեան (public-key cryptography) մէջ։ Վերացական հանրահաշիւի մէջ պարզ տարրերը եւ պարզ իտէալները պարզ թիւերու ընդհանրացուած ձեւերն են։

Սահմանում եւ օրինակներ

Բնական թիւը (1, 2, 3, 4, 5, 6 եւ այլն) կը կոչուի պարզ թիւ, եթէ անիկա մեծ է 1-էն եւ կարելի չէ զայն ներկայացնել իրմէ փոքր երկու բնական թիւերու արտադրեալի տեսքով։ Այն թիւերը, որոնք մեծ են 1-էն եւ պարզ չեն, կը կոչուին բաղադրեալ թիւեր։ Այլ խօսքով՝ n-ը պարզ է, եթէ n քանակութեամբ տարրերը կարելի չէ բաժնել մէկէն մեծ տարրեր պարունակող աւելի փոքր հաւասարաչափ խումբերու, կամ կարելի չէ n կէտերը դասաւորել ուղղանկիւնի մը տեսքով այնպէս, որ ուղղանկիւնին բարձրութիւնն ու լայնութիւնը ունենան մէկէն աւելի կէտեր։

Օրինակ՝ 1-էն 6 միջակայքին մէջ 2, 3 եւ 5 թիւերը պարզ են, քանի որ անոնք ուրիշ ոչ մէկ թիւի վրայ (բացի 1-էն եւ իրենցմէ) անմնացորդ կը բաժնուին։ 1-ը, ըստ սահմանման, պարզ չէ։ 4 = 2 \times 2 եւ 6 = 2 \times 3$ թիւերը բաղադրեալ են։

7-ը պարզ թիւ է, որովհետեւ առանց մնացորդի չի բաժնուիր 2, 3, 4, 5 կամ 6 թիւերէն ոչ մէկուն։

Բնական n թիւի մը բաժանարարները այն բնական թիւերն են, որոնց վրայ n-ը կը բաժնուի առանց մնացորդի։ Իւրաքանչիւր n բնական թիւի համար՝ 1-ը եւ n-ը բաժանարարներ են։ Եթէ թիւը ունի այլ բաժանարարներ ալ, ապա անիկա պարզ չէ։ Հետեւաբար, պարզ թիւերու համազօր սահմանումը հետեւեալն է․ ճիշդ երկու բաժանարար ունեցող թիւերը։ Քանի որ 1-ը ունի միայն մէկ բաժանարար, անիկա այս սահմանումով նոյնպէս պարզ չէ։ Մէկ այլ համազօր սահմանում է՝ n-ը պարզ է, եթէ անիկա մեծ է մէկէն եւ առանց մնացորդի չի բաժնուիր 2, 3, \dots, n-1 թիւերէն ոչ մէկուն։

Առաջին 25 պարզ թիւերն են (100-էն փոքր բոլոր պարզ թիւերը)․

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97։

Միակ զոյգ պարզ թիւը երկուքն է, քանի որ երկուքէն մեծ ցանկացած զոյգ թիւ կը բաժնուի 2-ի։ Հետեւաբար, 2-էն բացի բոլոր պարզ թիւերը կենտ են։ Տասնորդական համակարգին մէջ, 5-էն մեծ բոլոր պարզ թիւերը կ’աւարտին 1, 3, 7 կամ 9 թուանշաններով։ Մնացեալ թուանշաններով աւարտող թիւերը բաղադրեալ են, քանի որ 0, 2, 4, 6 եւ 8 թուանշաններով աւարտողները զոյգ են, իսկ 0-ով կամ 5-ով աւարտողները կը բաժնուին 5-ի։

Պարզ թիւերու բազմութիւնը յաճախ կը նշանակուի P կամ {P} տառով (լատ.՝ primus-էն):

$\mathbb {P}$ = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, ..} Մնացեալ բնական թիւերը մէկէն զատ կը կոչուին բաղադրեալ թիւեր:

Եւկլիդեսի Ապացոյցը

Եւկլիդեսը ապացուցած է, որ պարզ թիւերն անվերջ են՝

՛՛Պատկերացնենք, որ պարզ թիւերու քանակութիւնը վերջաւոր է։ Բոլոր պարզ թիւերը բազմապատկենք իրարով ու ստացուածին գումարենք մեկ։ Ստացուած թիւը կը բաժանուէ մեր ունեցած եւ ոչ մեկ պարզ թիւի, քանի որ բաժանումէն ստացուած մնացորդը միշտ մեկ պիտի ըլլայ։ Կը ստացուի, որ այդ թիւը պէտք է բաժնուի մեկ պարզ թուի, որը մէնք չենք ընդգրկած մեր պարզ թիւերու բազմութեան մէջ։ Ստացանք հակասութիւն։

Էրատոսթէնեսի Մաղը

Պարզ թիւերը բնական թիւերէն զատելու հնագոյն եղանակն առաջարկած է է յոյն թուաբանագէտ Էրատոսթէնեսը (մ.թ.ա. 264-192)։ Սկզբունքը հետեւեալն է՝ բնական թիւերու շարքին հերթականօրէն կը ջնջուին այն թիւերը, որոնք կը բաժնուին իրենց նախորդներէն գոնէ մէկուն վրայ։

Առաջին՝ 2 թիւը պարզ է, երկրորդը՝ 3-ը նոյնպէս, քանի որ չի բաժուիր 2-ի, 4-ը բաղադրեալ է, քանի որ կը բաժնուի մինչ այդ գտնուած 2 եւ 3 թիւերէն մէկուն (2-ի) վրայ, ուրեմն՝ 4-ը կը ջնջենք, 5-ը պարզ է, քանի որ չի բաժնուիր մինչ այդ գտնուած պարզ թիւերէն ոչ մէկուն վրայ եւ այդպէս շարունակ։

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31 ...

Ամէնամեծ Պարզ Թիւը

2017 թուականի 26 Դեկտեմբերի դրութեամբ յայտնի ամենամեծ պարզ թիւն է՝ 2^77232917-1-ը, որն ունի 23249425 տասնային նշան.