6.3: Нескінченність простих чисел

Last updated
Save as PDF

Page ID: 65513

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)

Родзинкою цього розділу є теорема 6.25, яка стверджує, що простих чисел нескінченно багато. Першим відомим доказом цієї теореми є елементи Евкліда (c. 300 до н.е.). Евклід заявив це наступним чином:

Пропозиція IX.20. Прості числа - це більше, ніж будь-яке призначене безліч простих чисел.

Є кілька цікавих спостережень, які слід зробити про пропозицію Евкліда та його докази. По-перше, зверніть увагу, що твердження теореми не містить слова «нескінченність». Греки сміливо ставилися до ідеї нескінченності. Таким чином, він довів, що простих чисел більше, ніж будь-яке задане скінченне число. Сьогодні ми б сказали, що їх нескінченно багато. Насправді Евклід довів, що існує більше трьох простих чисел і зробив висновок, що їх більше, ніж будь-якого скінченного числа. Хоча такий доказ не вважається дійсним в сучасну епоху, ми можемо пробачити Евкліду це менш суворе доказ; насправді його доказ легко перетворити на загальне, яке ви наведете нижче. Нарешті, доказ Евкліда був геометричним. Він розглядав свої числа як відрізки лінії з інтегральною довжиною. Сучасне поняття числа ще не розроблено.

Перш ніж боротися з доказом теореми 6.25, нам потрібно довести пару попередніх результатів. Доказ першого результату вам надано.

Теорема 6.23. Єдине натуральне число, яке ділить\(1\) це\(1\).

\(m\)Дозволяти натуральне число, яке ділить\(1\). Ми знаємо, що\(m\geq 1\) тому що 1 є найменшим натуральним числом. Так як\(m\) ділить\(1\), існує\(k\in \mathbb{N}\) таке, що\(1=mk\). З тих пір\(k\geq 1\), ми це бачимо\(mk\geq m\). Але\(1=mk\), і так\(1\geq m\). Таким чином, ми маємо\(1\leq m \leq 1\), що має на увазі те\(m=1\), що за бажанням.

Для наступної теореми спробуйте використати доказ протиріччя разом з теоремою 6.23.

Теорема 6.24. \(p\)Дозволяти просте число і нехай\(n\in \mathbb{Z}\). Якщо\(p\) ділить\(n\), то\(p\) не ділить\(n+1\).

Тепер ми готові довести наступну важливу теорему. Використовуйте доказ протиріччям. Зокрема, припустимо, що існує скінченно багато простих чисел, скажімо\(p_1, p_2,\ldots,p_k\). Розглянемо продукт всіх з них, а потім додаємо 1.

Теорема 6.25. Простих чисел нескінченно багато.

Ми завершуємо цю главу цікавою задачею, що включає прості числа. Ця проблема походить від Девіда Річесона (Коледж Дікінсона).

Проблема 6.26. Почніть з перших\(n\) простих чисел,\(p_1,\ldots, p_n\). Розділіть їх на два набори. \(a\)Дозволяти бути добутком простих чисел в одному наборі і нехай\(b\) бути добутком простих чисел в іншому наборі. Припустімо, що товар дорівнює 1, якщо набір порожній. Наприклад, якби\(n=5\), ми могли б\(\{2,7\}\) і\(\{3,5,11\}\), і так\(a=14\) і\(b=165\). Загалом, про що можна зробити висновок\(a+b\) і\(a-b\)? Сформуйте здогадки, а потім доведіть її.