质数某些定理

1.合数只有一种质因数拆解方式。

A为合数，A可分解为a的x0次*b的ⅹ1次*c的ⅹ2次……或a的y0次*b的y1次*c的y2次……，因A若为不同的质数整除，则质数可为其他质数整除，这是不可能的，不符合质数定义。只能是质数的次数不同，若第一种拆分中，某质数p的次幂为m，另一种拆分中，p的次幂为n，m>n，A/p的n次的两种拆分中，一种有p的m-n次，一种没有p，这是不可能的。假设不成立。

2.两正数小于某质数，两正数乘积不能整除这个质数。

设a、b为两正数，c为质数，a＜c，b

3.a、b不能被质数p整除，ab不能被p整除。a/p≠整数，p不是a的质因数，同理不是b的质因数。→p不是ab的质因数→ab/p≠整数。→a、b、c、d……不能被质数p整除，abcd……/p≠整数。

4.A被B整除，B的质因数A都有，且次数不超过A中的次数。

5.最大公约数，每个共同质因数在A、B、C……中最小次幂乘积。

6.最小公倍数，A、B、C……中所有质因数最高次幂的乘积。

7.a、b、c……都与K互质，其乘积与k互质。

8.a、b、c……互质且能整除k，→a、b、c……为k的质因数→abc……能整除k

9.m、n对模a、b、c……（互质)同余→a、b、c……整除m-n→abc……整除m-n

10.数A=a的x次幂*b的y次幂*c的m次幂……（a、b、c……为不同质数)，A=k的n次幂，→K的质因数也为a、b、c……→k=a的j次幂*b的p次幂*c的q次幂……→k的n次=a的nj次*b的np次*c的nq次……→nj=ⅹ，np=y，nq=m……→j=ⅹ/n，p=y/n，q=m/n……→A的每个质因数次幂可被n整除。

11.a、b、c……互质，且等于k的n次，a可写为l的α次*m的β次*p的γ次……（l、m、p……为质数）→a的1/n=l的α/n次*m的β/n次*p的γ/n次……→对b、c……同样适用。

12.a、b能被k整除，且关于模m同余→a/k=n1，b/k=n2，(a-b)/m=n3→(a-b)/k=n1-n2=n4→k与m都整除a-b，且k与m互质→(a-b)被km整除。若k、m有最大公约数e→(a-b)/km=(a/K-b/k)/m，分子分母同乘以1/e结果不变→(a/ke-b/ke)/(m/e)=(a-b)/km=整数。

13.若k与m互质，e与f关于模m同余→(e-f)/m=n→k(e-f)/m=kn→ke与kf关于模m同余(12的另一种表述)。

若a和m互质，e与f关于模m非同余→a不能被m整除，e-f不能被m整除→ae与af关于模m非同余。(12的逆定理)。→a与0到m-1中每个数相乘，并把乘积化简为相对模m的最小剩余，且各不相同，不超m。

14.m与a互质，ax+b与c关于m同余→(aⅹ+b-c)/m=k→(aⅹ-(c-b))/m=k→aⅹ与c-b关于模m同余，c-b关于模m的最小正剩余为e→(根据上条定理)有ⅹ