Просты лік

Просты лік — натуральны лік, які мае роўна 2 дзельнікі: самога сябе ды 1. Лікі, што маюць больш за 2 дзельнікі, называюцца састаўнымі. Паводле асноўнай тэарэмы арыфметыкі, кожны лік, большы за 1, можна прадставіць у выглядзе здабытку простых лікаў, прытым толькі адным спосабам (не ўлічваючы перастаноўкі множнікаў).

Паслядоўнасць простых лікаў

• Пачатак паслядоўнасці простых лікаў: 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...

• Простых лікаў бясконца шмат (даказаў Эўклід: хай колькасць простых лікаў канечная, але тады ніводзін з іх не дзеліць іхні здабытак, павялічаны на адзінку, а гэта супярэчнасць).

• Леанард Ойлер паказаў, што сума лікаў, адваротных простым, разбягаецца.

• Для кожнага натуральнага n ёсць просты лік p, не меншы за n і не большы за 2n (пастулат Бертрана).

• У арыфметычнай прагрэсіі a, a + q, a + 2q, a + 3q,..., дзе a і q ўзаемна простыя, існуе бясконца шмат простых лікаў (тэарэма Дырыхле).

• Найбольшым вядомым зараз простым лікам з'яўляецца лік Мерсена M_24036583, у яго дзесятковым запісе 7235733 лічбаў.

• З мноства простых лікаў можна выдзеліць адвольна доўгую концую паслядоўнасць простых лікаў, якая будзе адрэзкам арыфметычнай прагрэсіі. Гэта сцверджанне вядома пад назвай тэарэма Грына-Тао.

Размеркаванне простых лікаў

Асноўны артыкул: Тэарэма аб размеркаванні простых лікаў

Для функцыі размеркавання простых лікаў π(x) (якую азначаюць як колькасць простых лікаў, не большых за x) праўдзіцца асімптатычны стасунак:

$\lim_{x\to +\infty} \frac{\pi(x)}{x/\ln x} = 1.$

Гэта азначае, што колькасць простых лікаў, меншых за n, мае парадак $n / \ln n$.

Тэсты на простасць

Самы просты спосаб пабудовы спісу простых лікаў да пэўнага значэння — рэшата Эратасфэна. Для праверкі, ці з'яўляецца пэўны лік простым, доўгі час на практыцы ўжываліся толькі імавернасныя алгарытмы (напрыклад, тэст Мілера-Рабіна). У 2002 годзе быў знойдзены дэтэрмінаваны алгарытм палінаміяльнай складанасці. Для больш вузкіх класаў лікаў існуюць адмысловыя тэсты на простасць (напрыклад, тэст Люка-Лемера для лікаў Мерсена).

Простыя лікі ў тэорыі груп

• Колца рэштаў $\mathbb{Z}_p$ ёсць полем тады і толькі тады, калі p — просты лік.
• Характарыстыка концага поля — альбо 0, альбо просты лік.
• Калі G — концая група з pⁿ элементаў, то яна мае элемент парадку p.
• Калі pⁿ дзеліць парадак групы G, то G мае pk + 1 падгруп парадку pⁿ.

Неразвязаныя пытанні пра простыя лікі

• Гіпотэза Гальдбаха: ці можна кожны лік, большы за 2, раскласці ў суму двух простых?
• Праблема простых лікаў-блізнят: колькі існуе пар простых лікаў, рознасць між якімі роўная 2?
• Ці бясконца шмат простых лікаў Фібаначы? Простых лікаў Ферма? Простых лікаў выгляду n² + 1?
• Ці заўсёды знойдзецца просты лік паміж n² і (n + 1)²?

Практычнае выкарыстанне

На практыцы простыя лікі ўжываюцца ў крыптасістэмах з адкрытым ключом, у генератарах псеўдавыпадковых паслядоўнасцей.

Простыя лікі Сафі Жэрмэн

Просты лік p называецца простым лікам Сафі Жэрмэн, калі лік 2p + 1 таксама ёсць простым. Гэтыя лікі прыцягнулі ўвагу, таму што Сафі Жэрмэн (Sophie Germain, французская вучоная-матэматык, 1 красавіка 1776 – 27 чэрвеня 1831) даказала, што апошняя тэарэма Ферма выконваецца для такіх лікаў.

Першыя простыя лікі Сафі Жэрмэн:

2, 3, 5, 11, 23, 29, 41, 53, 83, 89, 113, 131, 173, 179, 191, 233, ...

Паслядоўнасць p, 2p + 1, 2(2p + 1) + 1, ... простых лікаў Сафі Жэрмэн называецца ланцугом Канігана (Cunningham chain) першага парадку. Кожны элемент гэтай паслядоўнасці (акрамя першага і апошняга) ёсць адначасова простым лікам Сафі Жэрмэн і бяспечным простым (англ.: safe prime, гэта просты лік выгляду 2p + 1, дзе p таксама просты).
Глядзі таксама простыя лікі Сафі Жэрмэн (па-англійску).

Спасылкі

• The Prime Pages(англ.)  — збор найбольшых вядомых простых лікаў
• PrimeGrid prime lists — усе простыя лікі, знойдзеныя ў рамках праекта PrimeGrid
• Геаметрыя простых і дасканалых лікаў(ісп.) 
• Geometrical connection between natural numbers and their factors