Сформулируйте и докажите основной закон арифметики натуральных чисел

Основной закон арифметики натуральных чисел состоит из двух частей и формулируется примерно так:

Часть 1. Любое натуральное число, кроме 1, можно представить в виде произведения простых чисел.
Часть 2. Причем данное число всегда будет раскладываться на один и тот же набор простых чисел; может различаться лишь их порядок.

Простое число

это натуральное число, которое имеет только два делителя – само себя и 1.

Составное число

это любое натуральное число, имеющее больше, чем два делителя.

Число 1 не является ни простым, ни составным.

В формулировке первой части основного закона арифметики натуральных чисел говорится, что закон касается всех натуральных чисел (за исключением 1). Это значит, что он относится и к простым числам. Даже если число простое, оно все-равно представимо в виде одного простого числа (самого себя). С другой стороны, тут отсутствует произведение. Можно было бы сказать «в виде произведения 1 и самого себя», но единица не является простым числом, что тоже нарушает определение.

Докажем первую часть закона по отношению к составным числам. Доказательство проведем «от обратного»: допустим, что существуют составные числа, которые нельзя разложить на произведение простых чисел, т. е. в ряде множителей есть другие составные числа.

Любое составное число имеет хотя бы два делителя, отличных от себя самого и единицы. Действительно, обозначим составное число из ряда множителей первого числа как n, его делитель, отличный от 1 и самого n, как m, а получившееся частное как q. Тогда n = mq. Т. е. m и q делители числа n. Причем ни m, ни q не равны самому числу n и 1. Но раз это делители, то они меньше числа n.

Пусть число m было наименьшим составным числом, входящим в ряды разложения других составных чисел. Это число может быть разложено только на простые, т. к. составного числа меньше его просто нет. Отсюда следует, что составное число всегда раскладывается на ряд простых чисел.

Теперь докажем вторую часть основного закона арифметики натуральных чисел: разные разложения составного числа на простые множители могут отличаться лишь порядком множителей, но не их количеством и составом.

Допустим, что существует число a, которое можно представить в виде разного набора простых множителей: a = p₁ × p₂ × … × p_m и a = q₁ × q₂ × … × q_n. Поскольку a делится на p₁, то во втором наборе множителей должно быть точно такое же число (пусть это будет q₂). Получаем a ÷ p₁ = p₂ × … × p_m и a ÷ q₂ = q₁ × … × q_n. Подобным образом сократим все одинаковые множители.

Если число a можно было бы представить в виде разного набора простых множителей, то в результате такого сокращения получилось бы число b (из числа a) в одном случае представленное из оставшихся множителей p, а во втором – из оставшихся q. Поскольку мы сократили все, что можно, то оставшиеся множители из разных наборов не равны друг другу. Причем это простые числа. Но перемножение одних простых чисел не может дать такого же результата, как при перемножении других простых чисел. Это следует из особенностей простых и взаимно простых чисел. [не очевидно]