计算机数学基础 数论简要笔记

基本概念：整除，因子，素数，合数，互质，公约数，最大公约数，欧几里德算法，模运算。

素数的个数是无穷的。

除法定理
令a为整数，d为正整数，则有唯一的整数q和r，其中0<=r<d，使得a=dq+r。

算术基本定理
任何一个大于1的自然数N，都可以唯一分解成有限个质数的乘积 N=(P_1^a1)*(P_2^a2)......(P_n^an) , 这里P_1<P_2<...<P_n是质数，其诸方幂 ai 是正整数。

If a and b are any integers, not both zero, then gcd(a,b) is the smallest positive element of set {ax+by:x,y belong to Z} of linear combination of a and b.

如果n是一个合数，则n必有一个小于或等于n的平方根的素因子。

ab=gcd(a,b)*lcm(a,b)

令a=bq+r,则gcd(a,b)=gcd(b,r)。
设d为a,b的公约数，则d|a,d|b,d|a-bq,d|r,推出d为b,r的公约数。
设d为b,r的公约数，则d|b,d|r,d|bq+r,d|a,推出d为a,b的公约数。
综上，(a,b)和(b,r)有共同的公约数。

gcd(a,b)=1且a|bc,则a|c。

如果p是素数，且p|A1A2A3...An,则对于某个i有p|Ai。

ac=bc mod m且gcd(c,m)=1,则a=b mod m。
ac=bc mod m -> m|(a-b)c , gcd(c,m)=1 -> m|a-b -> a=b mod m。

如果a和m互质，m>1，则存在a的模m逆。且这个逆模m是唯一的。

中国余数定理
令m1,m2,...mn为两两互质，则方程组
x=a1 mod m1
x=a2 mod m2
...
x=an mod mn
有唯一的模m=m1m2...mn的解。

中国余数定理的应用，可以用来做大整数的计算机算术运算。
令m1,m2,...mn为两两互质，m=m1m2...mn，则对任何一个a，0<=a<m，可以用一个n元组来表示。这个n元组为(a mod m1, a mod m2, ... , a mod mn)。

费马小定理
假如p是质数，且(a,p)=1，那么 a^(p-1) ≡１（mod p）