此外，在初等数论中还经常用到的一个工具，那就是鸽巢原理，也就是同等意义下的在组合数学中的抽屉原理 介绍完自然数和整数及其性质定理等数论基础后，下面来关注初等数论的一写重要方面，即整除、带余数除法、辗转相除法、素数、约数、最大公约数理论、算术基本定理等等整除既然是初等数论的基础内容，看似简单的整除，若要领略各中精髓以及其中之奥妙，仍需下一番苦功夫单从整除的定义就有各种解释方法： 1） 设a,b∈Z,a≠0,如果存在q∈Z,使得b=aq,那么就说b可被a整除，记作a∣b. 2） Z上定义一种关系R，令R={(a,b)∣a≠0.b∈Z}，且在使ax=b有解，称为Z上的整除关系任意的δ∈R，存在a,b∈Z，使得δ=（a,b）∈R,一般写成aRb,称为a与b有整除关系，也称a是b的约数，也称b是a的倍数 aRb令为a∣b,这就回到了第一种定义，其实这两种定义方式看似一样，其数学内涵却大有不同：第一种定义方法是从最原始的观点出发，也可说从“整除”的字面意思来定义，也是中学最常用的一种定义方式，因此只能算作一种简单明了的数学思维，并不能真正体现数学的高等数论尽管初等数论是一种初等思想去解决一些高等难题。
第二种定义方法则焦点于高等代数中的环、域定义环、域定义让我们的数学定义方式更加广泛，这是初等数学中所没有的，因此有的时候初等数学解决不了的问题就可以用此种定义去解决，这给了我们更广泛的思维空间对整除的各方面性质可以归纳如下： 1） 序关系 ≤ (N,<) 这来源于近似代数，故不做研究 2） 等价关系 ① aRa 自反关系 ② aRb =>bRa 对称关系 ③ aRb,bRc=>aRc 传递性 注意：整除不是等价关系 3） 整除具有线性可加性 a∣bi (1≤i≤n) ó a∣∑bixi xi∈Z 4） 整除可约性 a∣bó ma∣mb(m≠0) 5） 整除与符号无关 a∣bó∣a∣∣∣b∣ ó -a∣bóa∣-b 6） a∣b(b≠0)=>∣a∣≤∣b∣ 上面这些性质可以灵活的加以利用，其魅力就可显现出来： 已知a,b∈Z.a2+b2≠0,存在x,y∈Z使得ax+by=1.若a∣bq,则可证a∣q A ,b同例1存在ax+by=1 如果 a∣n,b∣n 则ab∣n 整除的这些性质应用可谓变幻无穷特别是在后面的素数、合数的相关性质方面及其证明中下面就来介绍一下关于素数的一些性质，当然介绍素数的同时还涉及到关于合数的问题。
点到部分再一一介绍从目前所学的内容来看关于素数的性质占了很大的比重，应该说是素数和整除的性质占了很大的部分，故彰显其重要性素数的概念与中学学的相差不大，只存在名称的扩充问题显然约（因、除）数，非显然约（因、除）数，真约（因、除）数的辨别问题当然须指出的是以后所介绍的素数一般指正的知道素数的概念后就应该思考一下关于素数的基本求法在课本随后的介绍中讲到了Eratosthenes筛法（在本书的第八章：素数分布的初等结果中有详细的讲解）来自书中的推论6即为该筛法的相关理论背景： 推论6：设整数a≥2. (ⅰ) 若a是合数，则必有不可约数p∣a,p≤a1/2 (Ⅱ) 若a=p1p2…ps的表示式，则必有不可约数p|a,p≤a1/s 其主要原理就来自于这个推论6当然此种意义下的Eratosthenes筛法是最简单的了对于它的推广应用还很多，比如说：如何找出1，2，…,N中至多两个素数的乘积的数？这就是推广意义下的应用，只是在推论6的理论下a的二分之一的情况改为三分之一的情况，这也可以看出推论6也可以推广的故我们知道该筛法有很多种应用情况，比如说至少两个素数的乘积的情况，至多三个的情况，至少三个的情况等等。
我们可以明显地观察出上面的这些解法是在有限的情况下来讨论的，故我们需要研究一下再不知道具体情况下的素数的一些情况 在不明确范围的情况下有很多种状况： 如：①设n≥1，2n+1是素数的必要条件是n=2k； ②2n-1是素数的必要条件是n为素数； 其证明也很简单：①若n≠2，则n=am,2不等于大于1的m 2n+1=(2a)m+1=(2a+1)((2a)m-1-(2a)m-2+…+1)便可得到 ②若n是合数，则n=am.a>1,m>1 2n-1=(2a)m-1=(2a-1)((2a)m-1+(2a)m-2+…+1)便可得到 其中数学中的一个著名定理是：不可约数（素数）有无穷多个除了课本中给出的证明方法以外，在习题中也有一些证明方式来进行证明： 如：1）设n≥0,Fn=2的2N次加上1（它称为Fermat数）再设m≠n,且d|Fn,则dFn由此推出素数有无穷多个，且可得到Fn+1=Fn … F0 +2 ; 2) 设F1 =2， An+1=A2n – AN +1,再设n≠m,若d|An,d>1,则 d 不整除于Am,由此推出素数有无穷多个，且可得到An+1=An … A1 +1.(设m>1,m|(m-1)!+1，可得到m是素数。
) 有了素数及整除的定义后，首先要考虑的就是公约数、最大公约数、公倍数、最小公倍数乍一看，这似乎就是中学内容不错，根据初等数论的低落脚点，这属于中学知识的衍生而已除了其定义是通过整除来定义以外，其他的性质也有适当的延伸其中较重要的一个就是：如果存在整数x1,x2,x2,…,xk,使得a1x1+a2x2+a3x3+…+akxk=1,则a1,a2,…,ak是既约的，即使互素的1） 这一定理在后面部分有着十分重大的作用如在实现建立最大公约数理论的第二个途径处：设a1,…,ak是不全为零的整数，有 1）（a1,a2,…,ak）=min{s=a1x1+a2x2+…+akxk;xj∈Z(1≤j≤k),s>0},即a1,…,ak 的最大公约数等于a1,…,ak的所有整系数线性组合组成的集合S中的最小正整数 2）一定存在一组整数x1,0, … ,xk,0 使得(a1, … ,ak )=a1 x1,0 + … + ak xk,0 ---------（2） 要论及上面这个定理得应用，下面可以举一个简单的例子： 若（a,b）=1则任一整数n必可表示为n=ax+by,x,y是整数由(a,b)=1及上定理（2）知存在x0,y0, 使得ax0+by0=1,因而取x=nx0,y=ny0, 即满足要求。
此题属于定理（1）（2）得综合运用，仍可想到的是在定理（2）有一种特殊情况，若其中的每一个元素均两两互素，那么情况（2）也就变成情况（1）了，因此情况（2）可以看作此种情况（1）的推广，情况（1）就看作情况（2）得特殊情况而已在构造一系列既约数方面应用得较多的方法就是下面这个方法： （a1/(a1,…,ak),…,ak/(a1,…,ak)）=1 关于最大公约数理论和最小公倍数理论的进一步性质推广，重在利用带余数除法在最大公约数理论部分讨论整数集合最重要的特性就在于其中可以实现带余数除法（也称带余除法或除法算法），它是初等数论中的证明中最重要、最基本、最直接的工具具体应用带余数除法时常取以下更灵活的形式： 设a,b是两个给定的整数，a≠0,再设d 是一给定的整数，那么，一定存在唯一的一对整数q1与r1，满足 b=q1a+r1,d≤r1<|a|+d. 此时，a|b的充要条件是a|r另外这个时候还应该灵活区分最小非负余数、绝对最小余数、最小正余数、余数此类应该在具体计算中有更广泛的作用，当然对于明确此类定义有很大的帮助依据带余数除法定义，可得出推论：设a>0,任一整数被a除后所得的最小非负余数是且仅是0,1,…,a-1这a个数中的一个。
这个推论最直接的用法就是整数分类以及进位制表示法，间接影响到辗转相除法 首先来看整除分类：j mod m称为j关于除数m所在的剩余类，则有0 mod a∪1 mod a∪…∪(a-1) mod a=Z,其中0≤i≠j≤（a-1）是集合j mod a 和 j’ mod a 不相交此时是利用全体整数按被a除后所得的最小非负余数分类，分成了两两不相交的a个类，这对诠释整除的含义有更积极的意义仔细观察，我们就会发现此种划分法与第三章中的“同余”有相似之处，最明显之处就是定义：a同余于模m，如果设m≠0,若m|a-b,即a-b=km，与 j mod m的定义j 关于除数m的所在剩余类，或许根本就是一个知识点确切的说j mod m 这个知识点属于同余的一个分支而已，即同余类（剩余类） 进位制的表示法可以看作是初等数论与计算机科学的一个交叉利用在计算机理论科学中，经常会遇到十进制、二进制、八进制、十六进制、甚至三十二进制之类的知识点而初等数论中的此处讲解得更为广泛、更为深刻 辗转相除法单独运用的情况一般较少，常用于综合分析，特别是与最大公约数理论的联合利用最大公约数理论与最小公倍数理论及其推广逐渐涉及到实际生活中的问题，例如四色问题的翻版。
至此，建立了整数集合Z中的最大公约数理论，特别是讨论了如何从各种不同的途径来建立这一理论，这是尤为重要的因为这主要不是为了利用不同的技。