这里介绍整数的一些基本知识，包括整除性，素因数分解和同余等。
一、整数的整除性
我们把1，2，3…，n，…叫做正整数，又叫自然数；把-1，-2，-3，…，-n，…叫做负整数；把正整数、负整数和零统称做整数。
显然，两个整数的和、差、积仍为整数，但两个整数相除（除数不为零），所得的商却不一定是整数。因此，许多整数问题都与整数除法有关，研究这些问题，就是整数的整除性。
我们用\[a\]表示不超过a的最大整数。例如，\[-2.5\]＝-3，\[3.4\]＝3，\[4\]＝4，\[π\]＝3。
关于\[a\]，显然下面不等式成立：
\[a\]≤a＜\[a\]＋1（1）
现在取a为有理数ab（a，b为整数，b＞0），则由（1）可以得到0≤ab-\[ab\]＜1或0≤a-b\[ab\]＜b由此可得a=\[ab\]＋r，0≤r＜b（2）
因此，我们得到下面的定理：
【定理1】（带余数除法）任给两个整数a，b＞0，必存在两个整数q及r，使得a＝qb＋r，0≤r＜b（3）
并且q及r是唯一的。
证明（2）已经指明存在性。我们只要证明唯一性就够了。
若还存在整数q1及r1，使得
a＝q1b＋r10≤r1＜b（4）
则从（3）和（4）可得
b（q-q1）＝r-r1
即有
b｜q-q1｜＝｜r-r1｜
因为r及r1为小于b的正数，所以｜r-r1｜＜b。若q≠q1，则有｜r-r1｜≥b，得出矛盾。故有q＝q1，从而推出r＝r1。
（3）中的q叫做不完全商，r叫做余数。
当r＝0时，（3）变成
a＝qb（5）
这时，我们就说b整除a，或a被b整除，b是a的因数，a是b的倍数。我们用b｜a表示b整除a，用b|\\a表示b不整除a。
现在我们给出整除的一些简单性质。其中，“｜”表示整除，例如a｜b表示b能够被a整除。
1）若a｜b，b｜c，则a｜c。
证明因为a｜b，b｜c，故有整数q1，q2使b＝q2a，c＝q2b。因此，c＝（q1q2）a。由于q1q2是整数，所以a｜c。
2）若a｜b，则a｜bc，c是任意整数。
证明因为a｜b，则有整数q使b＝qa，因此，。由于qc是整数，所以a｜bc。
3）若a｜b，a｜c，则a｜（b±c）。
证明因为a｜b，a｜c，则有整数q1，q2使b＝q1a，c＝q2a。因此，b±c＝（q1±q2）a。又（q1±q2）是整数，所以a｜（b±c）。
由（2）、（3）及数学归纳法，立得：
（4）若a｜bi，i＝1，2，…，n，则a｜（k1b1＋k2b2＋…＋knbn），ki，i＝1，2，…，n，是任意整数。
由（4）可推出：
（5）若在一个等式中，除某项外其余各项都是a的倍数，则此项也是a的倍数。
（6）若a｜b，b｜a，则b＝±a。
证明令a，b都不为零。因为a｜b，b｜a，则有整数q1，q2使b＝aq1，a＝bq2。因此a＝aq1q2。约去a得1＝q1q2。整数q1，q2的积为1，故此两个整数必同为1或-1，因而，b＝±a。
现在我们讨论两个整数的因数与倍数问题。
设a，b是两个数，若d是a的因数，也是b的因数，则d叫做a，b的一个公因数。a、b所有公因数中最大的一个叫做a、b的最大公因数，记作（a，b）。特别，若（a，b）＝1，则称a，b互素。
不难看出，a、b的公因数与｜a｜、｜b｜的公因数相同，因而有（a，b）＝（｜a｜，｜b｜）
因此，我们讨论最大公因数，不妨就非负整数去讨论。
现在介绍一个求最大公因数的方法——辗转相除法。这个方法不但可以用来求两个正整数的最大公因数，而且还可以借此推出最大公因数的一些重要性质。
设a，b是任意两个正整数。由带余数除法，我们可以得到下列等式：a＝bq1＋r1，0＜r1＜bb＝r1q2＋r2，0＜r2＜r1
（6）
rn-2＝rn-1qn＋rn，0＜rn＜rn-1
rn-1＝rnqn＋1＋rn＋1，rn＋1＝0
因为每进行一次带余数除法，余数至少减1，而b是有限的，所以我们最多进行b次带余数除法，可以得到一个余数为零的等式，即rn＋1＝0。上面的计算方法，叫做辗转相除法。这个方法是我国古代数学家首先创造的，在古算书里叫求一术。但在国外叫欧几里得除法。
【定理2】若a，b，c是三个不全为零的整数，且a＝bq＋c，则（a，b）＝（b，c）。
由整除性质5）及最大公因数的定义，这个定理是不难证明的。
现在我们证明：
【定理3】设a，b是任意两个正整数，则
（a，b）＝rn
证明利用（5）及定理2可以得到
rn＝（0，rn）＝（rn＋1，rn）＝（rn，rn-1）
＝…＝（r1，b）＝（a，b）
定理3给出一个求最大公因数的实际方法。当a，b中有一个为零时，（a，b）等于不为零那个数；当a，b都不为零，（a，b）＝rn。
推论若（a，b）＝d，则存在两个整数s，t，使as＋bt＝d。
下面给出最大公因数的两个重要性质：
设a，b是两个正整数，则
（1）（am，bm）＝（a，b）m，这里m为任意正整数。
（2）若d是a，b的任一公因数，则
ab，ab=（a，b）b
特别有
aa，b，ba，b=1
证明由（6）及定理2不难证明（1）。利用（1）的结果立即推出（2）。
现在给出互素的两个性质：
（1）若（a，b）＝1，a｜bc，则a｜c。
证明因为（a，b）＝1，由推论可知，存在整数s，t，使as＋bt＝1
从而
acs＋bct＝c（7）
由题设a｜bc，故a可以整除（7）的左端每一项，因此a｜c。
（2）若b与a1，a2，…，an都互素，则b与a1a2…an互素。
证明由题设及推论，对于ai、b存在整数si、ti，使bsi＋aiti＝1，i＝1，2，…，n把所有这n个式子乘起来，右边得1，左边有2n项，其中有一项包含a1a2…an，而其余各项都包含b。所以乘起来的式子可写成bs＋a1a2…anT＝1
由此可见，b和a1a2…an任何公因式必整除1，故两者互素。
下面研究最小公倍数。
设a，b，m是正整数。若a｜m，b｜m，则称m是a，b的一个公倍数。a，b所有公倍数中最小的一个叫做a，b的最小公倍数，记作\[a，b\]。
关于两个数的最大公因数与最小公倍数的关系有下面的定理【定理4】\[a，b\]=ab（a，b），特别地，若（a，b）＝1，则[a，b］＝ab（证明略）。
最大公因数及最小公倍数的概念可以推广到多于两个数的情形。
二、素数算术基本定理
定义：一个大于1的整数，如果它的正因数只有1及它本身，就叫做素数（或质数）；否则叫做合数。
以后我们用p，p1，p2，…表示素数。
由定义可以把自然数分为三类：1、素数和合数。
【定理5】设p为素数，a是任一整数，则或（p，a）＝1，或p｜a。
证明因为（p，a）｜p，由素数定义，或（p，a）＝1，或（p，a）＝p，即p｜a。
【定理6】设a1，a2，…，an是n个整数，p是素数。若p｜a1a2…an，则p至少整除a1，a2，…，an中的一个。
证明若P|/ai，i＝1，2，…，n，由定理5知（p，ai）＝1。再由互素性质2）得（p，a1a2…an）＝1，与题设矛盾。
【定理7】（算术基本定理）任一大于1的整数n，恰有一种方法分解成素因数的乘积。
证明要证n＞1必能分解成下面的形式
n＝p1p2…p3，p1≤p2≤…≤ps（8）
其中p1，p2，…，ps为素数，称为素因数，并且这种表示式是唯一的。
首先证明n一定能分解成（8）的形式。若n为素数，则（8）显然成立，若n为非素数，则必有n＝p1n1，1＜p1＜n1
这里素数p1为n的最小正因数。若n1为素数，则（8）已证；若n1为非素数，则有n＝p1p2n2，1＜n2＜n1＜n这里素数p2为n1的最小正因数。继续下去，可以得到n＞n1＞n2＞…＞1。这种过程最多不能超过n次，故最后得n＝p1p2…p2，p1＜p2＜…ps其中p1，p2，…，ps为素数。
其次证明（8）的表示法是唯一的。若n还可以分解成n＝q1q2…qt，q1＜q2＜…＜qt（9）
其中q1，q2，…，qt为素数，由（8）和（9）得到p1p2…ps＝q1q2…qt（10）
由定理6，存在pk（1≤k≤s）及q1（1≤l≤r）使q1｜pk，p1｜ql但pk，ql为素数，所以pk＝q1，ql＝p1。又p1≤pk，q1≤ql，故ql＝p1≤pk＝q1，即p1＝q1。因此，从（10）得p2p3…ps＝q2q3…qt同样可得p2＝q2。依此类推，最后得到s＝r，且pi＝qi（1≤i≤s）。唯一性得证。
推论任一整数n（n＞1）能够唯一地分解成n=pr11pPr22……Prn5（11）
其中p1，p2，…ps是素数，r1，r2，…，rs是正整数。（11）叫做n的标准分解式。
【定理8】（欧几里得）素数无穷多。
证明我们用反证法。若素数只有有限个，设为p1，p2，…，pn。令N＝p1p2…pn＋1
则N＞1，并且p1，p2，…，pn都不能整数N，故N无素因数，这是不可能的。