数论-唯一分解定理

唯一分解定理

• • 唯一分解定理
    • 最小剩余
      • 定理
      • 定义
      • 推论
    • 模
      • 定理
      • 证明
      • 推论
    • 唯一分解
      • 定理
      • 证明
        • 存在
        • 唯一
      • 总结
    • 参考

最小剩余

定理

设 a 和 b 为整数, b>0 ,则存在整数 q 和 r ,使得 a=qb+r,0≤r<b ,使 r 称为 b 除 a 所得的最小剩余

真确性无需证明,根据定理有如下定义:

定义

• 当 r 为0的时候,称 b 为 a 的因子, a 为 b 的倍数,记为 b|a .

• 若 b 为 a 的因子, b≠1,b≠a 这时称 b 为 a 的真因子.

若 b≠0,c≠0 ,有如下推论:

推论

• 若 b|a,c|b ,则 c|a ;

• 若 b|a, 则 bc|ac ;

• 若 c|d,c|e ,则对任意 m,n 有 c|dm+en .

---

模

定理

若集合 M 为整数的一个子集,对加减运算封闭,则称M为模,而任意一个非零模,必为一正整数的诸倍数组成的集合.

证明

设 d 为集合 M 中最小的元素,则模中其他的数必定为 d 的倍数,可以用反证法:

假设 n 不是d的倍数,则 n=kd+r,0<r<d .

因为 M 对加减法封闭,所以我们可以不断减去 d ,直至只剩下 r .

因为 0<r<d 与d是集合中最小的元素矛盾,故定理得证.

推论

• 存在整数 x,y ,使 (a,b)=ax+by

• 对于任何 x,y ,必有 (a,b)|ax+by .

• 若 c|a,c|a ,则 c|(a,b) .

  根据第一个推论又有如下推论:

  • 对于任何两个互质的数,那么存在 x,y 使得 ax+by=1

  • 若p为素数且 p|ab ,则 p|a 或者 p|b .

  对于第二个推论证明如下:

  若 p∤a (p不能整除a),所以 (a,p)=1 ,则根据定理,有整数 x,y

  ax+py=1

∴abx+pyb=b

∵p|ab

∴ab=kp

∴kp+pyb=b−−−>(k+yb)p=b

∴p|b

唯一分解

定理

对于任一自然数 n 皆可唯一的表示为素数之积 n=pa11pa22⋯pakk .

证明

存在

当 n 为素数,定理坑定c成立.当 n 不是素数时,设 p1 为 n 的最小真因子,容易证明 p1 为素数,

设 n=p1n1(1<n1<n) ,那么继续对 n1 重复以上步骤,不超过 n 次后,可得

n=p1p2⋯pl

唯一

设

n=pa11pa22⋯pakk=qb11qb22⋯qbkk,p1<p2<⋯<pk,q1<q2<⋯<qk

利用以上定理: 若p为素数且 p|ab ,则 p|a 或者 p|b .

可得对于每个 pi|n ,可得 pi|qb11qb22⋯qbkk 可以推得

pi|qbjj 又因为 pi,qj 是素数,可得

pi=qj 又因为 p1<p2<⋯<pk,q1<q2<⋯<qk

可得对于每个 pi 都有 qi 相等.

而若 ai≠bi

可得等式 pa11pa22⋯pai−bii⋯pakk=qb11qb22⋯qbi−1i−1qbi+1i+1⋯qbkk

左边含有 pi 而右边不含有 pi ,这是不可能的

可得 ai=bi

唯一性得证

总结

唯一分解定理是数论的基础,再以后的学习中会经常用到.

参考

<<算法数论>> 裴定一 祝跃飞 编著