Просты лік

(Перанакіравана з «Простыя лікі»)

Просты лікнатуральны лік, які мае роўна 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, ёсьць  . Для кожнага натуральнага n ёсьць просты лік p, ня меншы за n і ня большы за 2n (пастулат Бэртрана). У арытмэтычнай прагрэсіі a, a + q, a + 2q, a + 3q,..., дзе a і q узаемна простыя, існуе бясконца шмат простых лікаў (тэарэма Дырыхле). Найбольшы вядомы цяпер просты лік зьяўляецца лікам Мэрсэна M24036583, у яго дзесятковым запісе 7235733 лічбаў.

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

рэдагаваць

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

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

рэдагаваць

Нявырашаныя пытаньні адносна простых лікаў

рэдагаваць

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

рэдагаваць

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

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

рэдагаваць

Просты лік 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 таксама просты).

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

рэдагаваць

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