求不依赖素因数分解定理证明素数相关整除性引理的思路

嘿，这题我刚好有几个不用素因数分解的思路，都是从最基础的整除性质和素数定义出发的，完全符合你在PA里证明素分解定理的前置要求：

思路一：借助最大公约数（gcd）简化问题 #

• 先设 ( d = \gcd(a, b) )，把a和b拆成 ( a = d \cdot m )，( b = d \cdot n )，这里显然 ( \gcd(m, n) = 1 )（因为我们已经把最大公因子完全提出来了）。
• 把原条件转化一下：( a \mid pb ) 就变成 ( d \cdot m \mid p \cdot d \cdot n )，约掉d后得到 ( m \mid pn )；同理 ( b \mid pa ) 转化为 ( n \mid pm )。
• 因为 ( \gcd(m, n) = 1 )，结合 ( m \mid pn )，用欧几里得引理（这个引理不用素因数分解就能证：因为gcd(m,n)=1，存在整数s、t使得 ( sm + tn = 1 )，两边乘p得 ( smp + tnp = p )，而 ( m \mid pn ) 意味着 ( pn = km )，代入上式得 ( smp + tkm = m(sp + tk) = p )，所以 ( m \mid p )），可得 ( m \mid p )。同理可得 ( n \mid p )。
• 因为p是素数，m只能是1或者p，n也只能是1或者p。但如果m=p且n=p的话，( \gcd(m, n) = p \neq 1 )，和我们之前的设定矛盾，所以这种情况不存在。剩下的情况要么m=1（此时a=d，b=d·n，显然a|b），要么n=1（此时b=d，a=d·m，显然b|a），刚好覆盖了结论的两种情况。

思路二：反证法结合素数的核心性质 #

• 先假设结论不成立，也就是a不整除b，同时b也不整除a，然后推出矛盾。
• 从 ( a \mid pb ) 出发，因为a不整除b，结合素数p的核心性质（若p整除两个数的乘积，则p至少整除其中一个数），我们看 ( \gcd(a, p) )：因为p是素数，这个gcd只能是1或者p。
  • 如果 ( \gcd(a, p) = 1 )，那由 ( a \mid pb ) 且gcd(a,p)=1，用欧几里得引理直接可得 ( a \mid b )，这和我们“a不整除b”的假设矛盾；
  • 如果 ( \gcd(a, p) = p )，那就说明p整除a，设 ( a = p \cdot k )。把这个代入另一个条件 ( b \mid pa )，就得到 ( b \mid p \cdot p \cdot k = p^2k )。同时原条件 ( a \mid pb ) 变成 ( p \cdot k \mid p \cdot b )，约掉p后得 ( k \mid b )，那我们可以设 ( b = k \cdot l )。
  • 把 ( b = k \cdot l ) 代入 ( b \mid p^2k )，约掉k后得到 ( l \mid p^2 )。因为p是素数，l的可能取值只能是1、p、p²：
    • 若l=p²，那b=k·p² = p·(p·k) = p·a，显然a|b，和假设矛盾；
    • 若l=p，那b=k·p = a，这时候a和b互相整除，也和假设矛盾；
    • 若l=1，那b=k，而a=p·k = p·b，显然b|a，还是和假设矛盾。
• 所有可能的情况都导出了矛盾，说明我们的假设不成立，原命题必然成立。

备注：内容来源于stack exchange，提问作者Lèreau