Просты лік

Просты лік — натуральны лік, які мае роўна 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... Простых лікаў бясконца шмат (даказаў Эўклід: хай колькасьць простых лікаў канечная, але тады ніводзін зь іх ня дзеліць іх здабытак плюс 1, што немагчыма). Леанард Ойлер паказаў, што сума лікаў, адваротных простым, разьбягаецца. Вядома, што колькасьць простых лікаў, меншых за n, ёсьць $O(n/\ln n)$. Для кожнага натуральнага n ёсьць просты лік p, ня меншы за n і ня большы за 2n (пастулат Бэртрана). У арытмэтычнай прагрэсіі a, a + q, a + 2q, a + 3q,..., дзе a і q узаемна простыя, існуе бясконца шмат простых лікаў (тэарэма Дырыхле). Найбольшы вядомы цяпер просты лік зьяўляецца лікам Мэрсэна M_24036583, у яго дзесятковым запісе 7235733 лічбаў.

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

Самы просты мэтад пабудовы сьпісу простых лікаў да нейкага значэньня — рэшата Эратасфэна. Для задачы праверкі, ці зьяўляецца зададзены лік простым, доўгі час практычна ўжываліся толькі імавернасныя альгарытмы (напрыклад, тэст Мілера-Рабіна). У 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 таксама просты).

Вонкавыя спасылкі

Просты лік — сховішча мультымэдыйных матэрыялаў