Основная теорема арифметики. Существование.

[lampard]

Пока что не могу доказать существование при помощи алгоритма Евклида.

В Википедии написано:

Цитата:

Можно доказать основную теорему арифметики с помощью алгоритма Евклида Здесь алгоритм Евклида будет присутствовать не в явном виде, а будет использоваться следствие из него:

Наибольший общий делитель $n\cdot a$ и $n\cdot b$ есть $n$ раз взятый наибольший общий делитель $a$ и $b$.
Из данного следствия можно доказать теорему Евклида:

Если $p$ — простое число и произведение двух чисел делится на p, то хотя бы один из двух множителей делится на $p$.
Теперь используем данную теорему, чтобы доказать основную теорему арифметики.

Существование: является следствием теоремы Евклида. Для доказательства этой теоремы рассмотрим простое число $p$ и произведение $n \cdot a$ . Пусть $n\cdot a$ делится на $p$, но a не делится на $p$. Так как p — простое, то его единственными делителями являются $1$ и $p$. Тогда $1$ — единственный общий множитель $p$ и $a$. Следовательно, $NOD(n\cdot p; n\cdot a)=n$. Очевидно, что $n\cdot p$ делится на $p$. Следовательно, так как каждый общий делитель двух чисел также является и делителем их НОД, а $p$ является общим делителем $n\cdot p$ и $n\cdot a$, то $n$ делится на $p$.

Пока что не очень ясно -- как доказывается эта теорема:
"Если $p$ — простое число и произведение двух чисел делится на p, то хотя бы один из двух множителей делится на $p$."

Она сама по себе очевидна. Не очень ясно как доказать. Но попробую. Если $a\cdot b$ делится на $p$, то $a\cdot b=k\cdot p$.

Если $a$ и $b$ не делится на $p$, то и их произведение не может делится на $p$, потому как, если $a=n_1p+r_1$ и $b=n_2p+r_2$, то их произведение $a\cdot b=n_1n_2p^2+n_1pr_2+n_2pr_1+r_1r_2$, все слагаемые в этой сумме делятся на $p$, кроме $r_1r_2$, значит получаем противоречие, значит таки теорема доказано. Можно ли считать это доказательством теоремы?

[nnosipov]

lampard в сообщении #1002643 писал(а):

Если $a$ и $b$ не делится на $p$, то и их произведение не может делится на $p$, потому как, если $a=n_1p+r_1$ и $b=n_2p+r_2$, то их произведение $a\cdot b=n_1n_2p^2+n_1pr_2+n_2pr_1+r_1r_2$, все слагаемые в этой сумме делятся на $p$, кроме $r_1r_2$, значит получаем противоречие, значит таки теорема доказано. Можно ли считать это доказательством теоремы?

Конечно, нет. Вы же не объяснили, почему $r_1r_2$ не делится на $p$. Это не очевидно.

-- Сб апр 11, 2015 21:43:04 --

lampard в сообщении #1002643 писал(а):

Она сама по себе очевидна.

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

[lampard]

nnosipov в сообщении #1002651 писал(а):

lampard в сообщении #1002643 писал(а):

Если $a$ и $b$ не делится на $p$, то и их произведение не может делится на $p$, потому как, если $a=n_1p+r_1$ и $b=n_2p+r_2$, то их произведение $a\cdot b=n_1n_2p^2+n_1pr_2+n_2pr_1+r_1r_2$, все слагаемые в этой сумме делятся на $p$, кроме $r_1r_2$, значит получаем противоречие, значит таки теорема доказано. Можно ли считать это доказательством теоремы?

Конечно, нет. Вы же не объяснили, почему $r_1r_2$ не делится на $p$. Это не очевидно.

Спасибо!

$r_1r_2$ не делится на $p$, потому как $r_1$ не делится на $p$ и $r_2$ не делится на $p$. Значит среди множества делителей $a$ и $b$ нет числа $p$, значит среди их произведения тоже нет числа $p$, так как число $p$ -- простое. А это, по всей видимости, не есть доказательство.

Можете, пожалуйста, пнуть в нужном направлении.

[nnosipov]

lampard в сообщении #1002672 писал(а):

$r_1r_2$ не делится на $p$, потому как $r_1$ не делится на $p$ и $r_2$ не делится на $p$

Это эквивалентно самой теореме.

Доказательство, например, вот:

lampard в сообщении #1002643 писал(а):

Для доказательства этой теоремы рассмотрим простое число $p$ и произведение $n \cdot a$ . Пусть $n\cdot a$ делится на $p$, но a не делится на $p$. Так как p — простое, то его единственными делителями являются $1$ и $p$. Тогда $1$ — единственный общий множитель $p$ и $a$. Следовательно, $NOD(n\cdot p; n\cdot a)=n$. Очевидно, что $n\cdot p$ делится на $p$. Следовательно, так как каждый общий делитель двух чисел также является и делителем их НОД, а $p$ является общим делителем $n\cdot p$ и $n\cdot a$, то $n$ делится на $p$.

Это доказательство основано на алгоритме Евклида.

[gefest_md]

На ту же тему http://dxdy.ru/topic95773.html

Это

lampard в сообщении #1002643 писал(а):

так как каждый общий делитель двух чисел также является и делителем их НОД

тоже доказывается.

lampard в сообщении #1002643 писал(а):

Пока что не могу доказать существование при помощи алгоритма Евклида.

В цитате из википедии не вижу чтобы существование доказывалось при помощи алгоритма Евклида.

[lampard]

nnosipov в сообщении #1002678 писал(а):

Это доказательство основано на алгоритме Евклида.

Не пойму -- в каком месте тут алгоритм Евклида применен, хотя алгоритм Евклида знаю хорошо. Еще не понимаю -- как это доказывает существование. Что-то туплю.

Вот здесь доказательство хорошо понимаю http://www.pereplet.ru/nauka/Soros/pdf/0003_112.pdf, но там алгоритм Евклида не причем. А вот хотелось бы именно при помощи него.

[nnosipov]

lampard в сообщении #1002786 писал(а):

Не пойму -- в каком месте тут алгоритм Евклида применен

Алгоритм Евклида нужен для обоснования равенства $\gcd{(np,na)}=n\gcd{(p,a)}$ (это свойство НОД не является очевидным).

lampard в сообщении #1002786 писал(а):

Еще не понимаю -- как это доказывает существование.

О существовании чего идёт речь? Если о существовании разложения на простые множители, то алгоритм Евклида для этого не нужен. А теорема Евклида нужна для доказательства единственности разложения. В свою очередь, теорема Евклида доказывается на основе алгоритма Евклида (возможны разные схемы доказательства: например, так, как Вы нашли в википедии, или так, как в статье http://www.pereplet.ru/nauka/Soros/pdf/0003_112.pdf ).

-- Вс апр 12, 2015 11:46:54 --

lampard в сообщении #1002786 писал(а):

Вот здесь доказательство хорошо понимаю http://www.pereplet.ru/nauka/Soros/pdf/0003_112.pdf , но там алгоритм Евклида не причем.

Как это не при чём? Именно на его основе устанавливается фундаментальное свойство: если $ab$ делится на $c$ и $\gcd{(a,c)}=1$, то $b$ делится на $c$.

[lampard]

Спасибо, понятно!