Любое целое число имеет простой делитель

[CMTV]

Здравствуйте!

В самом простом доказательстве бесконечности множества простых чисел фигурируют утверждения следующего характера:

Цитата:

Значит, число должно делиться на некоторое простое число, не включённое в этот набор.

Цитата:

Но если оно составное, то должно при разложении на множители содержать простые множители.

Но ведь утверждения выше являются следствиями основной теоремы арифметики, которая доказывается уже после доказательства бесконечности множества простых чисел.
Я попытался доказать эти утверждения для любых целых чисел.
------
Теорема:
$ \forall z\in\mathbb{Z} \ \exists p \text{ — простое} : a\ \vdots \ p $ (любое целое число имеет простой делитель)

Доказательство:

Пусть $z\geqslant 0$.

Если $z = 0 \Rightarrow p = 2$.
Если $z$ — простое $\Rightarrow p=z$.
Если $z$ — составное, то имеем только два варианта:

1. $z$ — четное $\Rightarrow p = 2$

2. $z$ — нечетное, тогда $\exists k\in\mathbb{Z} \setminus \{z\}$ такое, что $z\ \vdots\ k$.
Если $k$ — простое $\Rightarrow p = k$. В противном случае $k$ тоже составное, нечетное и притом $k < z$.

Получаем конечную убывающую цепочку делителей $z$:

$$ z > k_1 > k_2 > \hdots > k_n > 0 $$

Возьмем минимальный положительный делитель — $k_n$. Это простое число, так как в противном случае существует $k_{n+1}$ делитель $z$, который меньше $k_n$ и больше 0. Но такого не может быть, так как $k_n$ — минимальный делитель. $\blacksquare$

Доказательство для $z<0$ аналогичное.

------

Правильно ли проведено доказательство? Может, есть более простые пути доказательства?

[mihaild]

Почти так, только надо брать делители большие $1$ (иначе вы придете к $k_n = 1$ и это ничем не поможет).
Можно либо так, либо сразу рассмотреть все делители $z$, отличные от $1$ (если $z \neq 0$, то их конечное число) и выбрать из них минимальный.

[CMTV]

mihaild в сообщении #1288580 писал(а):

Почти так, только надо брать делители большие $1$ (иначе вы придете к $k_n = 1$ и это ничем не поможет).

А разве мы придем к 1 в этой цепочке? Ведь вот это

mihaild в сообщении #1288580 писал(а):

Если $k$ — простое $\Rightarrow p = k$.

не позволит опуститься до нее...

[gris]

А почему Вы $0$ рассмотрели, а $1$ нет?
(Чисто формальный вопрос по начальной формулировке.)

[mihaild]

CMTV в сообщении #1288574 писал(а):

$z$ — нечетное, тогда $\exists k\in\mathbb{Z} \setminus \{z\}$ такое, что $z\ \vdots\ k$

Тут никаких ограничений на $k$ нет, поэтому можно взять $k=1$ и переход "если $k$ не простое, то $k$ составное" будет неверен. А еще четные и нечетные отдельно рассматривать не обязательно.
(понятно что это всё мелочи, но и рассуждение простое)

[vpb]

То, что любое натуральное число делится на некоторое простое --- это не следствие основной теоремы арифметики,
и не того, что простых чисел бесконечно много, а следствие того факта, что любое непустое множество натуральных чисел имеет наименьший элемент (что очевидно). В самом деле, пусть $z$ натуральное и $z>1$. Рассмотрим множество всех его делителей, отличных от $1$. Оно имеет наименьший элемент, скажем $p$. Если $p$ не простое, то любой его собственный делитель является делителем и для $z$, что противоречит минимальности $p$. Значит $p$ простое.

[CMTV]

gris в сообщении #1288587 писал(а):

А почему Вы $0$ рассмотрели, а $1$ нет?

mihaild в сообщении #1288588 писал(а):

Тут никаких ограничений на $k$ нет, поэтому можно взять $k=1$ и переход "если $k$ не простое, то $k$ составное" будет неверен.

Понял свою проблему. Я почему-то не задумывался о том, что 1 - не простое и не составное. Считал, что если число не простое, то оно составное и как-то не вспоминал про единицу.

vpb в сообщении #1288711 писал(а):

В самом деле, пусть $z$ натуральное и $z>1$. Рассмотрим множество всех его делителей, отличных от $1$. Оно имеет наименьший элемент, скажем $p$. Если $p$ не простое, то любой его собственный делитель является делителем и для $z$, что противоречит минимальности $p$. Значит $p$ простое.

Так действительно звучит короче и лаконичнее. Собственно, это именно то, о чем писал mihaild во втором сообщении.

Спасибо за замечания и указания. С этим разобрался)

[arseniiv]

vpb
Неясно, в каком смысле можно говорить «следствие не того, а этого» выше: есть какое-то вполне упорядоченное полукольцо, в котором простых элементов конечное число и само оно нефакториально? [Я не в курсе, есть ли хорошее обобщение всего этого с колец на полукольца, но, видимо, должно быть, раз всё начали с натуральных, и с первого взгляда ничего страшного происходить не должно.]

Потом, с другой стороны, кстати, берём $\mathbb Z$, оно не вполне упорядочено, а любое составное число всё же имеет простой делитель.

[CMTV]

arseniiv в сообщении #1288830 писал(а):

Потом, с другой стороны, кстати, берём $\mathbb Z$, оно не вполне упорядочено, а любое составное число всё же имеет простой делитель.

А это относится к доказательству в первом сообщении (с учетом поправок про 1 и необязательность разделения на чет/нечет, оговоренных выше)? Просто я пока не влезал в тему упорядоченности множеств и принимаю утверждения типа "найдется наименьший/наибольший элемент" на веру в тех случаях, когда это действительно очевидно.

[arseniiv]

arseniiv в сообщении #1288830 писал(а):

Потом, с другой стороны, кстати, берём $\mathbb Z$, оно не вполне упорядочено, а любое составное число всё же имеет простой делитель.

Я тут глупость сказал. Конечно, это никакой не контрпример — посылка ложна, импликация истинна.

CMTV в сообщении #1288846 писал(а):

А это относится к доказательству в первом сообщении (с учетом поправок про 1 и необязательность разделения на чет/нечет, оговоренных выше)?

Не, это мелкий методический частично оффтоп, не переживайте.

[vpb]

arseniiv в сообщении #1288830 писал(а):

Неясно, в каком смысле можно говорить «следствие не того, а этого» выше: есть какое-то вполне упорядоченное полукольцо, в котором простых элементов конечное число и само оно нефакториально? [Я не в курсе, есть ли хорошее обобщение всего этого с колец на полукольца, но, видимо, должно быть, раз всё начали с натуральных, и с первого взгляда ничего страшного происходить не должно.]

Я тут имел в виду в педагогическом смысле следует, то есть когда излагают основы элементарной теории чисел, то сначала идут простые утверждения о делимости, потом из них выводится, что каждое число имеет разложение на простые, а уже потом то, что простых бесконечно много, равно как и то, что разложение однозначно.

Насчет вполне упорядоченного полукольца не знаю, а кольцо, в котором есть разложение, притом есть лишь конечное число простых (с точностью до ассоциированности), и, кроме того, разложение не однозначно --- я думаю, такие есть.

CMTV в сообщении #1288846 писал(а):

Просто я пока не влезал в тему упорядоченности множеств и принимаю утверждения типа "найдется наименьший/наибольший элемент" на веру в тех случаях, когда это действительно очевидно

И это правильный подход. Не стоит без реальной нужды преждевременно погружаться в абстракции. Собственно, то, что писал arseniiv, это был вопрос ко мне, касающийся неких тонкостей, которые к Вашему исходному вопросу имеют лишь весьма отдаленное отношение.

[arseniiv]

vpb в сообщении #1289009 писал(а):

Я тут имел в виду в педагогическом смысле следует, то есть когда излагают основы элементарной теории чисел, то сначала идут простые утверждения о делимости, потом из них выводится, что каждое число имеет разложение на простые, а уже потом то, что простых бесконечно много, равно как и то, что разложение однозначно.

Ясно (и остаётся только согласиться). Что-то такое подозревал, но уточнить вряд ли было вредно.