如何证明大于1的自然数素因数分解的唯一性？求非归纳方法

当然有！其实算术基本定理唯一性的证明，除了强归纳，最直观的思路是反证法结合欧几里得引理，而且这个方法不用明确写出强归纳的递归步骤，更容易理解。我给你一步步拆解：

首先我们明确要证的核心：任何大于1的自然数n，若存在两种素因数分解：

n = p₁p₂…pₖ = q₁q₂…qₘ
其中所有pᵢ、qⱼ都是素数（我们可以先把它们按非降序排列，不影响结论），那么必然k=m，且对应位置的素数完全相同（p₁=q₁，p₂=q₂，…，pₖ=qₘ）。

步骤1：假设存在反例，取最小的那个 #

我们用反证法：假设存在大于1的自然数，它有两种不同的素因数分解。我们从这些数里挑出最小的那个n（这里用到自然数的「良序性」——任何非空的正整数子集都有最小元素，这是自然数的基本公理，很多时候不需要用归纳法来推导）。

步骤2：用欧几里得引理找到匹配的素数 #

因为n是最小反例，所以它的任何真因数（比如n/p₁）都只有唯一的素分解。现在看第一个分解里的素数p₁：

• p₁整除n，所以p₁必然整除第二个分解的乘积q₁q₂…qₘ。
• 根据欧几里得引理：如果一个素数p整除若干个数的乘积，那么它必然整除其中至少一个数。所以p₁一定整除某个qⱼ。
• 而qⱼ本身是素数，它的正因数只有1和自己，所以p₁必须等于qⱼ。

步骤3：推出矛盾，反例不存在 #

我们把p₁和qⱼ从两个分解里同时去掉，得到：
n/p₁ = p₂p₃…pₖ = q₁q₂…qⱼ₋₁qⱼ₊₁…qₘ
因为n/p₁ < n，而n是我们假设的最小反例，所以n/p₁的素因数分解必须是唯一的。这意味着剩下的素数序列必须完全一致——长度相同，对应位置的素数也相同。

那反过来推，原来的两个分解也必须完全一致，这就和我们“n有两种不同分解”的假设矛盾了。

所以不存在这样的反例，算术基本定理的唯一性得证。

补充：欧几里得引理的非归纳证明 #

如果你担心欧几里得引理用到归纳，其实它可以用贝祖定理来证明，而贝祖定理可以通过欧几里得算法（迭代过程，不是归纳）推导：

贝祖定理：如果a和b互质，那么存在整数x、y，使得ax + by = 1。
对于欧几里得引理，假设素数p整除ab，但p不整除a（因为如果p整除a，直接得证），那么p和a互质。根据贝祖定理，存在x、y使得px + ay = 1。两边乘以b得：pxb + aby = b。左边两项都能被p整除（p整除pxb，p整除ab所以p整除aby），因此p整除右边的b，引理得证。

内容的提问来源于stack exchange，提问作者Cocoboom