Узаемна простыя лікі. асновы

Падручнікі матэматыкі часам складаныя для ўспрымання. Сухі і выразны мова аўтараў не заўсёды даступны для разумення. Ды і тэмы там заўсёды ўзаемазвязаныя, взаимовытекающие. Для асваення адной тэмы даводзіцца падымаць шэраг папярэдніх, а часам і перагортваць увесь падручнік. Складана? Так. А давайце рызыкнем абыйсці гэтыя складанасці і паспрабуем знайсці да тэмы не зусім стандартны падыход. Зробім гэтакі экскурс у краіну лікаў. Вызначэнне, аднак, мы ўсё ж такі пакінем ранейшым, бо правілы матэматыкі адмяніць нельга. Такім чынам, узаемна простыя лікі - лікі натуральныя, з агульным дзельнікам, роўным адзінцы. Гэта зразумела? Цалкам.

Для больш навочнага прыкладу давайце возьмем колькасці 6 і 13. І тое, і іншае - дзелім на адзінку (узаемна простыя). А вось колькасці 12 і 14 - такімі не могуць з'яўляцца, паколькі дзеляцца не толькі на 1, але і на 2. Наступныя колькасці - 21 і 47 таксама не падыходзяць да катэгорыі "узаемна простыя лікі": іх можна падзяліць не толькі на 1, але яшчэ і на 7.

Абазначаюць узаемна простыя лікі так: (а, у) = 1.

Можна сказаць нават прасцей: агульны дзельнік (найбольшы) тут роўны адзінцы.
Для чаго нам такія веды? Прычын дастаткова.

Узаемна простыя лікі ўключаны ў некаторыя сістэмы шыфравання. Тыя, хто працуе з шыфрамі Хіла або з сістэмай падстановак Цэзара, разумеюць: без гэтых ведаў - нікуды. Калі вы чулі пра генератарах псеўдавыпадковых лікаў, то наўрад ці вырашыцеся адмаўляць: узаемна простыя лікі выкарыстоўваюцца і там.

Зараз пагаворым пра спосабы атрымання такіх лікаў. Колькасці простыя, як вы разумееце, могуць мець толькі два дзельніка: яны дзелім на саміх сябе і на адзінку. Скажам, 11, 7, 5, 3 - лікі простыя, а вось 9 - няма, бо гэты лік ўжо дзелім і на 9, і на 3, і на 1.

І калі а - лік простае, а к - з мноства {1, 2, ... а - 1}, то тады гарантавана (а, у) = 1, або узаемна простыя лікі - а і у.

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

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

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

у = р а + k

Калі, напрыклад, а = 71, р = 3, q = 10, то, адпаведна, у тут будзе роўны 713. Магчымы і іншы падбор, са ступенямі.

Складовыя колькасці, у адрозненне ад ўзаемна простых, дзеляцца і на сябе, і на 1, і на іншыя дні (таксама без астатку).

Іншымі словамі, натуральныя лікі (акрамя адзінкі) разбітыя на складовыя і простыя.

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

Самае вялікае простае лік знойдзена доктарам-афтальмолагам Марцінам Новаком, якія ўдзельнічалі ў праекце GIMPS (размеркавальныя вылічэнні) разам з іншымі энтузіястамі, якіх налічвалася каля 15 тыс. На разлікі сышло шэсць доўгіх гадоў. Было задзейнічана два з паловай дзясяткі кампутараў, якія знаходзяцца ў вочнай клініцы Новака. Вынікам тытанічнай працы і ўпартасці з'явілася лік 225964951-1, з Запісванне ў 7.816.230-дзесятковых знаках. Дарэчы, рэкорд самага вялікага ліку быў пастаўлены за паўгода да гэтага адкрыцця. І знакаў там было на паўмільёна менш.

У генія, якая хоча назваць лік, дзе працягласць дзесятковай запісу "пераскочыць" дзесяцімільённая адзнаку, ёсць шанец атрымаць не толькі сусветную славу, але і 100 000 даляраў. Дарэчы, за лік, якая пераадолела мільённую мяжу знакаў, Наян Хайратвал атрымаў меншую суму (50 000 даляраў).