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 /p n 有两种因数分解的方式，其中一种不含因数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 ，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 是某个方幂，例如k n ，那么，所有的指数α ，β ，γ ，…都能被n 整除。
因为数k 没有除a ，b ，c ，…外的质因数。令k 含α ′次因数a ，则k n 或A 含nα ′次因数a ，因此nα ′＝α 并且 是整数。与此类似， ，…也是整数。
21
当a ，b ，c ，…互质，而且乘积abc …是方幂，例如k n ，那么a ，b ，c ，…每个数都是n 次方幂。
令a ＝l λ m μ p π ，…，其中，l ，m ，p ，…都是不同的质数，由假设知，它们都不是数b ，c ，…的因数。因此乘积abc …含有λ 次因数l ，μ 次因数m ，…。由前一条知，λ ，μ ，π ，…都可以被n 整除，因此
是整数。对b ，c ，…同样成立。
我们的研究从这些关于质数的结论开始，现在转而探讨更接近我们目的的主题。
22
假设数a ，b 都能够被另一个数k 整除。若它们关于模m 同余，且m 与k 互质，则 和 关于相同的模同余。
由假设可知，a -b 可以被k 整除，也可以被m 整除，因此 （参见条目19） 可以被m 整除，即 （mod m ）。
如果让其他假设不变，令m 和k 有最大公约数e ，则 。因为 和 互质，且a -b 可以被k 和m 整除，所以 可以被 和 整除，因此可以被 整除，即 可以被 整除，也就意味着 。
23
若a 和m 互质，e 和f 相对于模m 非同余，则ae ，af 相对于模m 非同余。
这里只是条目22的逆定理。
显然，如果把a 与0到m -1中的每个整数相乘，并把每个乘积简化为对于模m 的最小剩余，那么这些最小剩余都不相等。并且，因为一共有m 个剩余，所有剩余都不大于m ，所以，从0到m -1的数都出现在这些剩余中。
24
给定数a ，b ；x 为不确定数或者是变量。表达式ax ＋b 对于模m 可以与任何数同余，其条件是m 与a 互质。
令与表达式ax ＋b 同余的数为c ，令c -b 对于模m 的最小正剩余为e 。从前一条定理可知，必定有一个值x ＜m 使得乘积ax 对于模m 的最小剩余为e ；令这个值为v ，则有av ≡e ≡c -b ，因此av ＋b ≡c （mod m ）。这就是需要做的。
25
任何用类似等式的方式提出两个同余的量的表达式，称为同余式 。如果它包含一个未知数，当能够求出一个值（根） 满足同余式时，这个同余式是可解 的。现在我们明白了同余式的可解与不可解的含义。提到等式的一些区分方法，也可以对同余方程使用。超越 同余方程的例子会在下文中出现；关于代数同余方程，按照未知数的最高次幂，可以分为一次，二次和更高次的同余方程。类似地，对于含几个未知数的同余方程组，我们可以探讨如何对其进行消元 。
