Доказательства основной теоремы арифметики

Ниже краткое, но полное доказательство основной теоремы арифметики (теорема о разложении на простые): каждый целый столк > 1 разлагается единственным образом на простые множители (с учётом порядка неважен).

1. Лемма Эвклида Если p является простым числом и p делит произведение ab, то p делит a или p делит b.

Доказательство: если p делит ab и не делит a, то gcd(p, a) = 1. Тогда существует такая линейная комбинация xp + ya = 1 (из Bezout). Умножим на b: b = xpb + yab. Так как p делит обе части, p делит b. Прямое следствие: если p не делит a, то p делит b; иначе p делит a.

2. Существование разложения (существование факторизации) Докажем по сильной индукции по n > 1.

• База: если n простое, то разложение есть: n.
• Шаг: пусть n составное, тогда n = ab, где 1 < a ≤ b < n. По предположению сильной индукции оба числа a и b раскладываются на простые множители. Значит n раскладывается на произведение этих простых множителей. Таким образом, для любого n > 1 существует разложение на простые.

3. Единственность разложения Пусть существует n > 1, которое имеет две различные разложения на простые: n = p1 p2 ... pk = q1 q2 ... ql, где pi и qj — простые, и эти разложения не совпадают по мультипликациям (последовательности путаются между собой). Выберем такое n минимальным по величине числом k + l или минимальным значением n.

По лемме Эвклида каждый из p1 делит произведение q1 q2 ... qk. Следовательно, p1 делит некоторый qj. Так как qj — простое число, получаем p1 = qj.

Умножим обе стороны разложения и разделим общий простой фактор p1 с обеих сторон: n / p1 = p2 p3 ... pk = q1 ... q_{j-1} q_{j+1} ... ql.

Слева это строго меньшая по величине целая часть, чем n, следовательно, по минимальности выбранного контрпримерa, разложения для n/p1 должны быть одинаковыми (до перестановки). Следовательно, после удаления совпавшего простого фактора мы получаем, что оставшиеся простые множители на обеих сторонах совпадают, и то же верно и для p1. Это противоречие с предположением о различии двух разложений.

Значит, двух разных разложений не существует, и разложение на простые уникально (с учётом перестановки факторов).

Итого: каждая целая система n > 1 имеет единственное разложение на простые множители (порядок не учитывается).

Дополнительные замечания и варианты presentations

• Можно формулировать и как "для любого n > 1 существует разложение n = ∏ pi с кратностью ai" и доказать существование и уникальность по аналогии, где каждое простое число встречается в разложении с некоторой степенью.
• Важное условие: считать 1 единицей и не считать 1 простым; единицы можно отклонить, поскольку они не влияют на разложение.
• Альтернативный путь к единственности: доказать, что Z является областью целых чисел, в которой факторизация в простые является уникальной (с использованием леммы Эвклида и принципа математической индукции). В более общей алгебре это обобщается в понятие уникального факторизационного домена (UFD).
• Связанные задачи: доказать лемму Эвклида отдельно, привести примеры разложения на простые для конкретных чисел (например, 360 = 2^3 · 3^2 · 5), обсудить примеры, где сходится или расходится уникальность в других кольцах (например, в кольцах, не являющихся UFD).

Если хотите, могу привести подробное решение в виде контролируемых шагов на конкретном примере или навести ещё несколько вариантов доказательства (например, через условие минимального counterexample или через принцип восходящего множества). Также могу подготовить конспект для экзамена с ключевыми формулировками и типовыми вопросами.