第1节 关于质数、因数等的初步定理
13
定理
两个正数如果都小于某个质数，则它们乘积不能被这个质数整除。
设p为质数，若正数a＜p，则找不到任何小于p的正整数b，使得ab≡0（mod p）。
证明
若定理错误，则存在数b，c，d，…，都小于p，使得ab≡0，ac≡0，ad≡0，…（mod p）。令b为其中最小的数，比b更小的数都不具备这个性质。显然b＞1，因为如果b＝1，则ab＝a＜p（通过假设）并且无法被p整除。既然p是质数，则它不能被b整除，但p处于b的两个连续倍数之间，即mb和（m＋1）b。令p-mb＝b′，b′是正数且b′＜b。现在，因为假设ab≡0（mod p），有mab≡0（参见条目7）。使ap≡0减去之，则a（p-mb）＝ab′≡0，即b′为数b，c，d，…中的某个数，且比它们中最小的数更小，这是荒谬的，证明完毕。
14
如果a和b都不能被质数p整除，则乘积ab也不能被p整除。
设α，β是数a，b对于模p的最小正剩余。它们都不是0（通过假设）。如果ab≡0（mod p），则αβ≡0，因为ab≡αβ。但这与前一条定理矛盾。
欧几里得已经在他的《几何原本》（第7章，32页）中证明了这则定理。但是我们不想忽略这条定理，因为很多现代作者对这条定理要么论证不充分，要么完全忽略了这条定理；而且这个简单的案例可以让我们理解方法的本质，以后要用同样的方法解决更加艰深的问题。
1570年的《几何原本》首版英译本
《几何原本》全书共13章，由欧几里得于约公元前300年写成，书中主要讨论了平面几何（第1—6章）、数论（第7—9章）、无理数（第10章）和立体几何（第11—13章）。此书是现代数学的基础，在西方，它是仅次于《圣经》而流传最广的书籍。
15
如果数a，b，c，d，…都不能被质数p整除，则它们之积也不能被p整除。
根据前一条定理，ab不能被p整除；因此abc也不能被p整除；类似地，abcd，…也不能被p整除。
16
定理
一个合数只能用一种方式拆分为质因数的乘积。
证明
由基本知识知道，任何合数可以拆分为质因数的乘积，但是，它一般被错误地、理所当然地认为这种拆分不能通过几种不同的方式。假设一个合数A＝aαbβcγ…，其中a，b，c，…为不相等的质数，除此之外还可以用其他方式拆分为质因数。首先，在第2种质因数体系中，不可能出现除了a，b，c，…之外的任何其他质数，因为由质数a，b，c，…组成的合数A不可能被任何其他质数整除。类似地，在第2种质因数体系中任何质因数a，b，c，…都不能缺失，否则就不能整除A（参见条目15）。那么这两种将合数A拆分为质因数的方式的不同只在于某些质因数出现的次数比另外质因数多。令其中某个质因数为p，在第1种因数分解中出现m次，在第2种因数分解中出现n次，令m＞n。现在从每个质因数体系中去掉n次p，结果p在一个系统中出现m-n次，在另一个出现0次。即，对合数A/pn有两种因数分解的方式，其中一种不含因数p，另外一种含m-n个因数p，这与上面的结论矛盾。
17
因此，如果合数A是合数B，C，D，…的乘积，可知B，C，D，…的所有质因数，全都是A的因数，而且每个因数在A的因数分解中出现的次数和在B，C，D，…的因数分解中出现的总次数是相等的。因此，可得一种可以判定B是否整除A的方法。B能够整除A的条件是，在A和B的因数分解中，B中所含的质因数在A中都有，且B中质因数出现的次数不超过在A中出现的次数。如果这两者任意一条不能满足，则B不能整除A。
从组合演算中可知，如上文a，b，c，…是不同质数，A＝aαbβcγ…，则A有（α＋1）（β＋1）（γ＋1）…个不同的除数，包括1和它自己。
18
如果A＝aαbβcγ…，K＝kκlλmμ…，质数a，b，c，…，k，l，m，…都各不相同，那么A和K没有除了1之外的公约数。换句话说，它们之间互质。
给定许多个数A，B，C，…，它们的最大公约数可以按如下方式找到。使所有的数分解为它们的质因数，从这些质因数中提取出A，B，C，…共有的质因数（如果一个都没有，则这些数没有公约数）。然后记下每个质因数在A，B，C，…中出现的次数，或者说记下每个质因数在A，B，C，…中的方幂数。最后给每个质因数赋予其在A，B，C中出现的最小方幂之后，它们的乘积就是要求的最大公约数。
求最小公倍数时，...
例如：令A＝504＝23×32×7，B＝2880＝26×32×5，C＝864＝25×33。对于A，B，C，有公共因数2，3，最小方幂分别为3，2，则最大公约数为23×32＝72；所有质数分别为2，3，5，7，最大方幂分别为6，3，1，1，则最小公倍数为26×33×5×7＝60480。
因为证明简单，所以此处省略。而且，从基本知识可知如何将数A，B，C，…进行因数分解。
19
如果数a，b，c，…都和某个数k互质，则它们的乘积abc…也和k互质。
因为数a，b，c，…与k都没有公共的质因数，而且因为乘积abc…中没有属于a，b，c，…的质数之外的质数，因此乘积abc…与k没有公共质因数。因此从前文知，k与abc…互质。
如果数a，b，c，…互质，且每个数都可以整除数k，则它们的乘积能整除k。
从条目17、18可以容易得出这条结论。因为，如果p是乘积abc…中出现了π次的质除数，可知，数a，b，c，…中的某个数必定含有相同的质除数π次。因此k也包含p——这个整除k的数——π次。相似地，对乘积abc…的所有其他质除数也成立。
因此，如果两个数m和n都对于几个模a，b，c，…同余，且这几个模互质，那么，这两个数也对于模的乘积同余。因为m-n能够被a，b，c，…中的每一个整除，m-n也可以被它们的乘积整除。
最后，若a和b互质，且ak能被b整除，则k也能被b整除。因为ak既能被a整除，又能被b整除，它也能被ab整除，即：
20
假设a，b，c，…为互不相等的质数，且A＝aαbβcγ…，如果A是某个方幂，例如kn，那么，所有的指数α，β，γ，…都能被n整除。
因为数k没有除a，b，c，…外的质因数。令k含α′次因数a，则kn或A含nα′次因数a，因此nα′＝α并且
