Numri i thjeshtë

**Numër i thjeshtë ** - quhet numri natyror i cili ka pikërisht 2 pjesëtues të ndryshëm, vetveten dhe numrin 1. Të gjithë numrat e tjerë natyrorë përveç numrit 1 quhen numra të përbërë. Të gjithë numrat natyrorë përveç 1 mund të zbërthehen në shumëzues të thjeshtë pra mund të shkruhen si prodhim i numrave të thjeshtë ose 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 1000

: 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, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997

## Zbërthimi i numrit natyror në faktore 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 faktorëve. 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&nbsp;978&nbsp;189 shifra në sistemin dhjetor dhe është numër që i përket klasës së numrave të Merseneit (M43112609). 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 108 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ëton 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 :

# *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
# *Problemi i dytë*: A ka pafund shumë ,,numra binjak,, Dy numra të thjeshtë janë binjak nëse ndryshimi në mes tyre është 2.
# *Problemi i tretë*: Ndërmjet numrave n^2 dhe (n + 1)^2 gjithmonë ka një numër të thjeshtë? Hipoteza e Legendreit
# *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 
* *Гальперин Г.* «Просто о простых числах» , «Квант», №&nbsp;4, 1987
* «Алгоритмические проблемы теории чисел», глава из книги «Введение в криптографию» nën redaktimin e В. В. Ященко
* *Василенко О. Н.* «Теоретико-числовые алгоритмы в криптографии»
* *Черемушкин А. В.* «Лекции по арифметическим алгоритмам в криптографии»
* *Кноп К.* «В погоне за простотой»

## Referime 
:

http://mathworld.wolfram.com/AKSPrimalityTest.html

EFF Cooperative Computing Awards

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