Numri i thjeshtë

Teorema themelore e aritmetikës thotë se ç'do numër natyror më i madh se 1, mund të paraqitet në mënyrë të vetme si prodhim i numrave të thjeshtë duke mos e pasur parasysh renditjen e faktoreve. Në këtë mënyrë përfundojmë se numrat e thjeshtë janë përbërësit elementar të numrave të natyror.

Sita e Eratostenit, sita Sundarama dhe sita e Atkinit japin një mënyrë të thjeshtë për gjetjen e listës së numrave të thjeshtë d.m.th. ndarjen apo sitjen e tyre nga bashkësia e numrave natyral.

Procesi i caktimit të thjeshtësisë së një numri natyral mjaft të madh nuk është aq i thjeshtë prandaj algoritmi i cili e përcakton se një numër është i thjeshtë apo jo quhet test i thjeshtësisë. Ekzistojnë bashkësi testesh polinomiale por të shumtët prej tyre bazohen në teorinë e gjasës. Vetëm në vitin 2002 u zbulua testi i thjeshtësisë AKS ^[1], i cili provon thjeshtësinë e një numri natyral sado të madh por algoritmi i tij polinomial është shumë i komplikuar dhe e vështirëson përdorimin e tij në praktikë.

Për disa klasë numrash ekzistojnë teste të thjeshtësisë që janë mjaft efektiv. P.sh për caktimin e thjeshtësisë se numrave të Mersenneit përdoret testi i thjeshtësisë i ashtuquajtur testi Lucas−Fermat dhe për numrat Fermat testi i Pepinit.

Euklidi vërtetoi se ekzistojnë pafund numra të thjeshtë ai këtë vërtetim e dha në veprën e tij Elementet (libri IX, teorema 20). Vërtetimi është shumë i thjesht por mjaft domethënës:

Supozojmë të kundërtën, pra se bashkësia e numrave të thjeshtë është e fundme. I shumëzojmë ato numra dhe atij prodhimi ia shtojmë numrin 1. Ky numër i fituar në këtë mënyrë është i ndryshëm nga të gjithë numrat e thjeshtë dhe nuk plotpjesëtohet me asnjërin prej tyre sepse gjatë pjesëtimit me cilindo prej tyre jep mbetjen 1. D.m.th ky numër duhet të pjesëtohet me një numër të thjeshtë i cili nuk është në bashkësinë fillestare sepse në të kundërtën edhe vetë është i thjeshtë.

Matematikanët kanë dhënë edhe vërtetime tjera njëri prej tyre i përket Leonhard Eulerit i cili tregoi se shuma e të gjithë numrave reciprok të numrave të thjeshtë është e pafundme pra është një seri divergjente që do të thotë se bashkësia e numrave të thjeshtë është e pafundme.

Është vërtetuar edhe teorema për shpërndarjen e numrave të thjeshtë e cila thotë se numra të thjeshtë më të vegjël se numri i caktuar natyral ${\displaystyle n}$ , të cilën e shënojmë me ${\displaystyle \pi (n)}$ , është e barabartë me ${\displaystyle n/\ln(n)}$ .

Numri më i madh i thjeshtë nuk ekziston por numri më i madh i thjeshtë i njohur deri më sot (shtator 2008) është numri ${\displaystyle 2^{43112609}-1}$ i cili përmban 12 978 189 shifra në sistemin dhjetor dhe është numër që i përket klasës së numrave të Merseneit (M_43112609). Ai u zbulua më 23 gusht 2008 në universitetin e Kalifornisë UCLA të Los Anxhelosit.

Për gjetjen e numrit të thjeshtë me më shumë se 10⁸ shifra në sistemin dhjetor Electronic Frontier Foundation shkurt EFF ofron shpërblimin prej 150000 dollarësh^[2] .

• Nëse ${\displaystyle p}$ - është numër i thjeshtë, dhe ${\displaystyle p}$ pjesëton ${\displaystyle ab}$ , atëherë ${\displaystyle p}$ e pjesëton ${\displaystyle a}$ ose ${\displaystyle b}$ . Këtë e vërtetoi Euklidi.
• Unaza e mbetjeve ${\displaystyle \mathbb {Z} _{n}}$ është fushë(mat) atëherë dhe vetëm atëherë nëse ${\displaystyle n}$ — është numër i thjeshtë.
• Karakteristika e ç'do fushe është 0 ose numër i thjeshtë.
• Nëse ${\displaystyle p}$ - është numër i thjeshtë dhe ${\displaystyle a}$ është numër natyral atëherë ${\displaystyle a^{p}-a}$ pjesëtohet me ${\displaystyle p}$ (Teorema e vogël Fermat).
• Numri natyral ${\displaystyle p>1}$ është i thjeshtë atëherë dhe vetëm atëherë nëse ${\displaystyle (p-1)!+1}$ plotpjesëtohet me ${\displaystyle p}$ (Teorema e Wilsonit).
• Ç'do numër i thjeshtë më i madh se 3 mund të shkruhet në trajtën ${\displaystyle 6k+1}$ , ose në trajtën ${\displaystyle 6k-1}$ , ku ${\displaystyle k}$ - është një numër natyral i çfarëdoshëm.
• Nëse ${\displaystyle p>3}$ është i thjeshtë atëherë ${\displaystyle p^{2}-1}$ plotpjesëtohet me 24.

Edhe sot me gjithë përpjekjet e bëra dhe përparimin e madh në lidhje me teorinë e numrave të thjeshtë ekzistojnë shumë probleme të hapura dhe hipoteza disa nga këto hipoteza i paraqiti Edmund Landau në kongresin e pestë ndërkombëtar të matematikanëve ku ai veçoi katër probleme të pazgjidhura ^[3]:

1. Problemi i parë: Ç'do numër çift më i madh se 2 mund të shkruhet si shumë e dy numrave të thjeshtë dhe ç'do numër tek më i madh se 5 mund të shkruhet si shumë e tre numrave të thjeshtë. Problemi i Goldbachut
2. Problemi i dytë: A ka pafund shumë ,,numra binjak,, Dy numra të thjeshtë janë binjak nëse ndryshimi në mes tyre është 2.
3. Problemi i tretë: Ndërmjet numrave ${\displaystyle n^{2}}$ dhe ${\displaystyle (n+1)^{2}}$ gjithmonë ka një numër të thjeshtë? Hipoteza e Legendreit
4. Problemi i katërt: Ka pafund shumë numra të thjeshtë të trajtës ${\displaystyle n^{2}+1}$ ?

Prej problemeve tjera të hapura e përmendim se nuk dihet se nëse në vargun e numrave të Fibonaccit ka pafund shumë numra të thjeshtë.

Numrat e thjeshtë shumë të mëdhenj të rendit ${\displaystyle 10^{300}}$ kanë zbatim në Kriptografi për konstruktimin e H-tabelave dhe për gjenerimin e numrave të pseudorastësishëm.

• Гальперин Г. «Просто о простых числах», «Квант», № 4, 1987
• «Алгоритмические проблемы теории чисел», глава из книги «Введение в криптографию» nën redaktimin e В. В. Ященко
• Василенко О. Н. «Теоретико-числовые алгоритмы в криптографии»
• Черемушкин А. В. «Лекции по арифметическим алгоритмам в криптографии»
• Кноп К. «В погоне за простотой»

^[3]:

[1]

EFF Cooperative Computing Awards

• PrimeGrid prime lists — të gjithë numrat e thjeshtë të gjetur në kuadër të projektit PrimeGrid
• Геометрия простых и совершенных чисел
• Онлайн Утилита для Проверки и Поиска Простых Чисел