Numri i thjeshtë

Numër i thjeshtë - quhet numri natyral i cili ka pikërisht 2 pjesëtues të ndryshëm vetveten dhe numrin 1. Të gjithë numrat tjerë natyral përveç numrit 1 quhen numra të përbërë. Të gjithë numrat natyral përveç 1 mund të zbërthehen në shumëzues të thjeshtë pra mund të shkruhen si prodhim i numrave të thjeshtë ose eventualisht i fuqive të tyre. Me studimin e vetive të numrave të thjeshtë merret dega e matematikës që quhet Teoria e numrave.

Më poshtë japim listën e numrave të thjeshtë jo më të mëdhenj se 113

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, 101, 103, 107, 109, 113

Zbërthimi i numrit natyror në shumëzues të 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 shumëzuesve. Në këtë mënyrë përfundojmë se numrat e thjeshtë janë përbërësit elementar të numrave të natyror.

Теsti i thjeshtësisë

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 , 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.

Sa numra të thjeshtë ekzistojnë?

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 $n$, të cilën e shënojmë me $\pi(n)$, është e barabartë me $n/\ln(n)$.

Numri më i madh i thjeshtë i njohur

Numri më i madh i thjeshtë nuk ekziston por numri më i madh i thjeshtë i njohur deri më sot (shtator 2008) është numri $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 .

Disa veti të numrave të thjeshtë

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

Probleme të hapura

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 :

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 $n^2$ dhe $(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 $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ë.

Zbatimi i numrave të thjeshtë

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

Literatura

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

Referenca

:

[1]

EFF Cooperative Computing Awards

Lidhje të jashtme

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