Асновы тэорыі лікаў
Тэорыя лікаў — гэта раздзел матэматыкі, які вывучае ўласцівасці цэлых лікаў. Нягледзячы на ўяўную прастату — бо цэлыя лікі ўключаюць проста …, -2, -1, 0, 1, 2, … — тэорыя лікаў мае надзвычай багатую структуру. Многія важныя паняцці ў сучаснай матэматыцы, крыптаграфіі і інфарматыцы заснаваныя на фундаментальных ідэях тэорыі лікаў , такіх як дзялімасць, простасць і параўнанне. У гэтым артыкуле разглядаюцца асноўныя асновы тэорыі лікаў: дзялімасць і алгарытм Еўкліда, простыя лікі і іх фактарызацыя , арыфметыка па модулю, а таксама некаторыя складаныя прымяненні і напрамкі.
1. Цэлыя лікі і асноўныя аперацыі
Тэорыя лікаў звычайна працуе з мноствам цэлых лікаў, якія пазначаюцца ℤ. Асноўнымі аперацыямі, якія выкарыстоўваюцца, з'яўляюцца складанне, адніманне і множанне. У адрозненне ад рацыянальных або рэальных лікаў, дзяленне на цэлыя лікі не заўсёды прыводзіць да цэлага ліку. Менавіта тут паняцце дзялення з астаткам становіцца цэнтральным.
Адно з важных суадносін у тэорыі лікаў — гэта дзялімасць. Для цэлых лікаў (a) і (b) мы пішам (a + b), калі існуе цэлы лік (k) такі, што (b = ak). Напрыклад, (3 + 12), таму што (12 = 3 × 4), але (5 + 12), таму што няма цэлага ліку (k), для якога (12 = 5k).
Дзялімасць мае наступныя асноўныя ўласцівасці:
– Калі \(a \mid b\) і \(a \mid c\), то \(a \mid (b+c)\) і \(a \mid (bc)\).
– Калі \(a \mid b\), то для кожнага \(k\) цэлага ліку \(a \mid (bk)\).
– Калі \(a \сярэдні b\) і \(b \сярэдні c\), то \(a \сярэдні c\).
Гэтыя простыя ўласцівасці служаць інструментамі для доказу многіх сцвярджэнняў пра цэлыя лікі.
2. Алгарытм дзялення
Тэарэма дзялення сцвярджае: для кожнага цэлага ліка \(a\) і дадатнага цэлага ліка \(b\) існуюць унікальныя цэлыя лікі \(q\) і \(r\) такія, што:
\[
a = bq + r,\quad 0 \le r < b \]. Тут \(q\) называецца дзеллю, а \(r\) — астаткам. Прыклад: калі \(a=29\) і \(b=5\), то \(29 = 5\cdot 5 + 4\), так што \(q=5\) і \(r=4\). Гэта паняцце важнае, бо яно з'яўляецца асновай Аперацыя па модулю і алгарытм Еўкліда для знаходжання НАД. 3. Найбольшы агульны дзельнік (НАД) і алгарытм Еўкліда Для двух цэлых лікаў (a) і (b) (абодва не роўныя нулю) найбольшы агульны дзельнік або НАД, які пазначаецца як (НАД(a,b)), — гэта найбольшы дадатны цэлы лік, які дзеліць іх абодва. Найбольш эфектыўны спосаб вылічэння НАД — гэта алгарытм Еўкліда. Згодна з тэарэмай аб дзяленні, калі: [ a = bq + r ], то: [ НАД(a,b) = НАД(b,r) ] Гэты працэс паўтараецца, пакуль астача (r) не будзе роўная 0. На апошнім этапе НАД — гэта апошні ненулявы дзельнік. Хуткі прыклад: знайсці (НАД(48,18)). – (48 = 18\cdot 2 + 12\) – (18 = 12\cdot 1 + 6\) – (12 = 6\cdot 2 + 0\) Тады (НСД(48,18)=6\). Алгарытм Еўкліда вельмі важны, таму што ён хуткі нават для вялікіх лікаў, што робіць яго вельмі карысным у вылічэннях. 4. Лінейныя камбінацыі і тоеснасць Безу Адным з фундаментальных вынікаў з'яўляецца тоеснасць Безу: для цэлых лікаў (a) і (b), якія не роўныя нулю, існуюць цэлыя лікі (x) і (y) такія, што: [НСД(a,b) = ax + by] Гэта азначае, што НСД можна запісаць як лінейную камбінацыю (a) і (b). Значэнні (x) і (y) можна знайсці з дапамогай пашыранага алгарытму Еўкліда. Точнасць Безу з'яўляецца ключавой у рашэнні: – лінейнага дыяфантава ўраўнення \(ax+by=c\), – знаходжання яго адваротнага модуля (важна ў крыптаграфіі). 5. Простыя лікі і фактарызацыя Просты лік — гэта дадатны цэлы лік, большы за 1, які мае толькі два дадатныя дзельнікі: 1 і самога сябе. Такія лікі, як 2, 3, 5, 7, 11, з'яўляюцца простымі. Лікі, большыя за 1, але не простыя, называюцца састаўнымі, напрыклад, 12, 21, 35. Найбольш вядомай канцэпцыяй з'яўляецца асноўная тэарэма арыфметыкі: кожны цэлы лік \(n>1\) можна адназначна (да парадку) запісаць у выглядзе здабытку простых лікаў:
\[
n = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k}
\]
Місальня:
\[
360 = 2^3 \cdot 3^2 \cdot 5
\]
Гэтая ўнікальнасць фактарызацыі з'яўляецца асновай многіх складаных тэм, у тым ліку крыптаграфіі RSA, якая абапіраецца на складанасць фактарызацыі вялікіх лікаў.
6. Кангруэнтнасць і арыфметыка па модулю
Арыфметыка па модулю вывучае лікі, заснаваныя на астачы ад дзялення. Мы кажам:
\[
a \equiv b \pmod{m}
\]
Калі \(m \mid (ab)\), гэта азначае, што \(a\) і \(b\) маюць аднолькавы астатак пры дзяленні на \(m\).
Прыклад: \(17 \equiv 5 \pmod{12}\), таму што \(17-5=12\) дзеліцца на 12. Па модулю 12, 17 і 5 лічацца эквівалентнымі.
Кангруэнтнасць мае тыя ж уласцівасці, што і звычайныя аперацыі:
– Калі (a = b mod{m}) і (c = d mod{m}), то
(a+c = b+d mod{m}) і (ac = bd mod{m}).
Арыфметыка па модулю вельмі карысная для:
– вызначаць перыядычныя заканамернасці,
– праверыць кратныя,
– распрацоўка эфектыўных вылічальных алгарытмаў,
– і сучасная крыптаграфія.
7. Адваротныя па модулю і кангруэнтныя ўраўненні
Лік (a) мае адваротны модуль (m), калі існуе лік (x) такі, што:
\[
ах \equiv 1 \pmod{m}
\]
Гэта адваротнае лік існуе тады і толькі тады, калі \(\gcd(a,m)=1\). Напрыклад, лік 3 мае адваротнае лік па модулю 7, таму што \(3\cdot 5=15\equiv 1 \pmod{7}\), таму яго адваротнае лік роўна 5.
Паняцце адваротнага модуля спрашчае рашэнне такіх ураўненняў, як:
\[
ах \equiv b \pmod{m}
\]
Калі існуе адваротная велічыня \(a^{-1}\), то рашэнне можна атрымаць, памнажаючы абедзве часткі:
\[
x \equiv a^{-1} b \pmod{m}
\]
8. Малая тэарэма Ферма і тэарэма Эйлера
Два вядомыя вынікі ў элементарнай тэорыі лікаў:
1. Малая тэарэма Ферма: калі \(p\) — простае лік, а \(a\) не дзеліцца на \(p\), то:
\[
a^{p-1} \equiv 1 \pmod{p}
\]
2. Тэарэма Эйлера (абагульненне): калі \(\gcd(a,m)=1\), то:
\[
a^{\varphi(m)} equiv 1 \pmod{m}
\]
дзе \(\varphi(m)\) — гэта функцыя тот'ена Эйлера (колькасць лікаў паміж 1 і \(m\), якія ўзаемна простыя з \(m\)).
Гэтыя тэарэмы ляжаць у аснове розных крыптаграфічных метадаў і метадаў хуткага вылічэння па модулю.
9. Пашыраныя праграмы і інструкцыі
Нягледзячы на тое, што спачатку гэта было простае пытанне пра цэлыя лікі, тэорыя лікаў цяпер стала шырокай галіной. Яе прымяненне ўключае:
– Крыптаграфія: RSA, крывыя Дыфі-Хелмана і эліптычныя крывыя выкарыстоўваюць уласцівасці простых лікаў, кангруэнтнасці і адваротнага модуля.
– Інфарматыка: хэшаванне, генератары выпадковых лікаў і алгарытмы вылічэнняў вялікіх лікаў.
– Камбінаторыка і тэорыя кадавання: пабудова кодаў з карэкцыяй памылак і дыскрэтных структур.
Пасля гэтых асноў часта вывучаюцца дадатковыя тэмы, такія як нелінейныя дыяфантавы ўраўненні, квадратычныя рэшткі, алгебраічная тэорыя лікаў і размеркаванне простых лікаў.
Закрыццё
Асновы тэорыі лікаў грунтуюцца на паняццях дзялімасці, НАД, простых лікаў і параўнання. Ад алгарытму Еўкліда да арыфметыкі па модулю, кожная ідэя фарміруе аснову для разумення структуры цэлых лікаў і адкрывае шлях для рэальных ужыванняў, асабліва ў лічбавую эпоху. Авалоданне гэтымі элементарнымі паняццямі дае магутныя інструменты для аналізу задач дыскрэтнай матэматыкі і паглыблення ў больш глыбокія тэмы сучаснай тэорыі лікаў.
