Евклидова теорема

Евклидова теорема — темелен исказ во теоријата на броеви што тврди дека има бесконечен број прости броеви. Постојат неколку познати докази за оваа теорема.

Евклидов доказ

Евклид го изнел доказот во своето дело Елементи (книга IX, став 20).^[1] Истиот е парафразиран подолу.^[2]

Нека е дадено кое било конечно множество природни броеви p₁, p₂, ..., p_n. Ќе се покаже дека има барем уште еден прост број што го нема во списокот. Нека производот на сите прости броеви во множеството биде P = p₁p₂...p_n. Нека q = P + 1. Тогаш q е или не е прост број:

Ако q е прост, тогаш има барем еден број (q) кој е прост и не е во првичното множество.
Ако q не е прост, тогаш некој прост број p го дели q. Кога овој број p би бил во множеството, тогаш тој би го делел P (бидејќи P е производ на сите броеви во множеството); но p го дели P + 1 = q. Ако p го дели P и q, тогаш p би морал да ја дели разликата^[3] овие два броја, што е (P + 1) − P или поедноставно 1. Како ниеден прост број не го дели 1, p не може да биде во множеството.Ова значи дека мора да постои барем уште еден прост број покрај оние што се веќе во множеството.

Ова докажува дека за секое конечно множество прости броеви има прост што не е во тоа множество, и затоа мора да има бесконечно многу прости броеви.

Често погрешно се наведува дека Евклид го докажал своето тврдење со доведување до контрадикција, тргнувајќи од претпоставката дека почетното множество ги содржи сите прости броеви, или дека содржи n најмали прости броеви, наместо произволно конечно множество прости броеви.^[4] Наместо да се сведува на противречност, доказот на Евклид покажува дека секое конечно множество го има наведеното својство. Од ова не следи противречност, но ниту еден од елементите на множеството не може да има својство да биде делител на број 1.

Постојат неколку варијации на доказот на Евклид, вклучувајќи го следново:

Факториелот n! на позитивниот цел број n е делив со секој цел број од 2 до n, бидејќи е производ од сите овие броеви. Затоа, n! + 1 не е дели ниту со еден од целите броеви од 2 до n, вклучително и n (дава остаток 1 кога ќе се подели со кој било од нив). Затоа, n! + 1 е или прост број, или е делив со прост број поголем од n. Во двата случаја, за секој позитивен цел број n, постои најмалку еден прост број поголем од n. Заклучокот е дека има бесконечно многу прости броеви.^[5]

Ојлеров доказ

Вториот доказ, што го осмислил швајцарскиот математичар Леонард Ојлер, се потпира на основната теорема на аритметиката: дека секој цел број може на единствен начин да биде претставен како производ на прости броеви. Ако множеството се состои од сите прости броеви, Ојлер тврди дека:

\prod _{p\in P}{\frac {1}{1-1/p}}=\prod _{p\in P}\sum _{k\geq 0}{\frac {1}{p^{k}}}=\sum _{n}{\frac {1}{n}}.

Првата еднаквост произлегува од формулата за геометриски ред во секој член на производот. Втората еднаквост е посебен случај на формулата за Ојлеров производза Риманова зета-функција. За да се покаже ова, неопходно е да се распредели производот по збир:

{\begin{aligned}\prod _{p\in P}\sum _{k\geq 0}{\frac {1}{p^{k}}}&=\sum _{k\geq 0}{\frac {1}{2^{k}}}\times \sum _{k\geq 0}{\frac {1}{3^{k}}}\times \sum _{k\geq 0}{\frac {1}{5^{k}}}\times \sum _{k\geq 0}{\frac {1}{7^{k}}}\times \cdots \\[8pt]&=\sum _{k,\ell ,m,n,\cdots \geq 0}{\frac {1}{2^{k}3^{\ell }5^{m}7^{n}\cdots }}=\sum _{n}{\frac {1}{n}}\end{aligned}}

во резултатот, секој производ од цели броеви се појавува точно еднаш, така што според основната теорема на аритметиката, збирот е еднаков на збирот на сите цели броеви.

Збирот од десната страна е хармониски ред, кој дивергира. Затоа, производот лево мора исто така да дивергира. Бидејќи секој член во производот е конечен, бројот на членови мора да биде бесконечен; затоа, мора да има бесконечно многу прости броеви.

Поврзано

Теорема за прости броеви

Белешки и наводи

↑ James Williamson (превод и коментар), The Elements of Euclid, With Dissertations, Clarendon Press, Oxford, 1782, стр 63.
↑ Прецизната формулација на Евклидовото тврдење гласи: „Простите броеви се побројни од кое било предложено мноштво прости броеви“. Во доказот од претпоставката дека постојат барем три прости броја, Евклид дедукува постоење на четврт.
↑ Во општ случај, за секои три цели броја a, b, c ако $a\mid b$ и $a\mid c$ , тогаш $a\mid (b-c)$ .
↑ Michael Hardy and Catherine Woodgold, "Prime Simplicity", Mathematical Intelligencer, том 31, број 4, есен 2009, стр. 44–52.
↑ Bostock, Linda; Chandler, Suzanne; Rourke, C. (1 ноември 2014.). Further Pure Mathematics (англиски). Nelson Thornes. стр. 168. ISBN 9780859501033. Проверете ги датумските вредности во: |date= (help)

Надворешни врски

„Euclid's Theorem“ од Ерик В. Вајсштајн — MathWorld (англиски)

Euclid's Elements, Book IX, Prop. 20 (Euclid's proof, on David Joyce's website at Clark University)

[1] James Williamson (превод и коментар), The Elements of Euclid, With Dissertations, Clarendon Press, Oxford, 1782, стр 63.

[2] Прецизната формулација на Евклидовото тврдење гласи: „Простите броеви се побројни од кое било предложено мноштво прости броеви“. Во доказот од претпоставката дека постојат барем три прости броја, Евклид дедукува постоење на четврт.

[3] Во општ случај, за секои три цели броја a, b, c ако $a\mid b$ и $a\mid c$ , тогаш $a\mid (b-c)$ .

[4] Michael Hardy and Catherine Woodgold, "Prime Simplicity", Mathematical Intelligencer, том 31, број 4, есен 2009, стр. 44–52.

[5] Bostock, Linda; Chandler, Suzanne; Rourke, C. (1 ноември 2014.). Further Pure Mathematics (англиски). Nelson Thornes. стр. 168. ISBN 9780859501033. Проверете ги датумските вредности во: |date= (help)

[1]

[2]

[3]

[4]

[5]