Просты лік
Зьвесткі зь Вікіпэдыі — вольнай энцыкляпэдыі.
Просты лік — натуральны лік, які мае роўна 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 / lnn). Для кожнага натуральнага n ёсьць просты лік p, ня меншы за n і ня большы за 2n (пастулат Бэртрана). У арыфмэтычнай прагрэсыі a, a + q, a + 2q, a + 3q,..., дзе a і q ўзаемна простыя, існуе бясконца шмат простых лікаў (тэарэма Дырыхле). Найбольшы вядомы зараз просты лік зьяўляецца лікам Мерсэна M24036583, у яго дзесятычным запісе 7235733 лічбаў.
[рэдагаваць] Тэсты на простасьць
Самы просты мэтад пабудовы сьпісу простых лікаў да нейкага значэньня — рэшата Эратасфэна. Для задачы праверкі, ці зьяўляецца зададзены лік простым, доўгі час практычна ўжываліся толькі імавернасныя альгарытмы (напрыклад, тэст Мілера-Рабіна). У 2002 годзе быў знойдзены дэтэрмінаваны альгарытм полінаміяльнай складанасьці. Для больш вузкіх клясаў лікаў існуюць спэцыфічныя тэсты на простасьць (напрыклад, тэст Люка-Лемэра для лікаў Мерсэна).
[рэдагаваць] Простыя лікі ў тэорыі групаў
- Кольца рэштаў
зьяўляецца полем тады й толькі тады, калі p — просты лік. - Характарыстыка канечнага поля — альбо 0, альбо просты лік.
- Калі G — канечная група з pn элемэнтаў, то яна мае элемэнт парадку p.
- Калі pn дзеліць парадак групы G, то G мае pk + 1 падгрупаў парадку pn.
[рэдагаваць] Нявырашаныя пытаньні адносна простых лікаў
- Гіпотэза Гальдбаха: ці можна кожны лік, большы за 2, раскласьці ў суму двух простых?
- Праблема простых лікаў-блізьнятаў: колькі йснуе параў простых лікаў, рознасьць між якімі роўная 2?
- Ці ёсьць бясконца шмат простых лікаў Фібаначы? Простых лікаў Фэрма? Простых лікаў выгляду n2 + 1?
- Ці заўсёды знойдзецца просты лік паміж n2 ды (n + 1)2?
[рэдагаваць] Практычнае выкарыстаньне
На практыцы простыя лікі ўжываюцца ў крыптасыстэмах з адкрытым ключом, у генэратарах псэўдавыпадковых пасьлядоўнасьцяў.
[рэдагаваць] Простыя лікі Сафі Жэрмэн
Просты лік 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 таксама просты).
Глядзі таксама Простыя лікі Сафі Жэрмэн (па-ангельску).
