算术基本定理(唯一分解定理) 有感与浅见
[引自《现代密码学》《初等数论》《信息安全数学基础》]
-索引:①算术基本定理证明 ②[良序集N+]在数论证明的强有力性 ③最大公因子的线性组合形式 ④数学归纳法 ⑤算术基本定理的相关应用
-算术基本定理
(1)定理内容:每个大于1的正整数，都可以被唯一地写成素数的乘积
(2)定理证明:(先引入两个引理)
①引理α:如果a，b，c∈N+，满足gcd(a，b)=1且a|bc，则a|c
证明:由于gcd(a，b)=1，存在x，y∈Z，使得ax+by=1()
等式()两边乘以c，得acx+bcy=c
有定理λ:p|x，p|y，z=ex+fy，则p|z
根据定理λ:a|a，a|bc，t=acx+bcy，则a|t
因为t=acx+bcy=c
由等式acx+bcy=c得a|c，引理α证毕
②引理β:如果p整除a1，a2，…，an，其中p为素数，且a1，a2，…，an∈N+，则存在i∈Z,1≤i≤n，使得p整除ai
证明:(数学归纳法)
(丨)n=1的情况是平凡的
(Ⅱ)假定结果对n成立
(Ⅲ)考虑n+1个整数的积a1a2…anan+1能够被素数p整除，由此得有gcd(p，a1a2…an)=1或gcd(p，a1a2*…an)=p成立
(i)如果(p，a1a2*…an)=1
根据引理α:a，b，c∈N+，满足gcd(a，b)=1且a|bc，则a|c
因为(p，a1a2*…an)=1且p|[(a1a2*…an)an+1]
则有p|an+1
(ii)另一方面，如果p|(a1a2…an)=p，由归纳假设，存在1≤i≤n，使得p|ai
因此，对于某个满足1≤i≤n+1的i有p|ai
引理β证毕
③算术基本定理证明:(反证法)
存在性:
假定某个正整数不能被写成素数的乘积
根据非空正整数集的良序性质:
设n是这样的整数中最小的一个
如果n是素数，显然它是素数的乘积，即一个素数n，所以n一定是一个合数
设n=ab，其中1<a<n，1<b<n
由于n是不能被写成素数乘积的整数中最小的一个，又a<n和b<n，得a和b一定可以写成素数的乘积
因此，n=ab也为素数的乘积。得出矛盾，原命题得证
唯一性:
设n有两种不同的素数分解形式
n=P1P2*…Ps=Q1Q2*…Qt
其中P1,P2,…,Ps和Q1,Q2,…Qt为素数
且P1≤P2≤…≤Ps,Q1≤Q2≤…≤Qt
在这两个分解式中约去相同的素数，得到
Pi1Pi2*…Piu=Qj1Qj2*…*Qjν
因为约去相同素数，等式左边的素数与右边的不同，其中u≥1,ν≥1。然而这与引理β产生矛盾
根据引理β，一定存在某个整数k使得Pi1|Qjk，这是不可能的，因为每个Piu与Qjν是不同的素数。
因此，正整数n的素因子分解是唯一的。
综上所述，算术基本定理证毕
-算术基本定理应用
大因数分解的困难性，基于数论的密码学就是基于已知的算法不能很好地进行大数因子分解。
