基础知识
最大公约数与最小公倍数是数论中的一个重要的概念，这里我们主要讨论两个整数互素、最大公约数、最小公倍数等基本概念与性质。
定义1.（最大公约数）设
不全为零，同时整除的整数（如
）称为它们的公约数。因为不全为零，故只有有限多个，我们将其中最大一个称为的最大公约数，用符号（）表示。显然，最大公约数是一个正整数。
当（）＝1（即的公约数只有）时，我们称
与互素（互质）。这是数论中的非常重要的一个概念。
同样，如果对于多个（不全为零）的整数，可类似地定义它们的最大公约数（）。若（）＝1，则称互素。请注意，此时不能推出两两互素；但反过来，若（）两两互素，则显然有（）＝1。
由最大公约数的定义，我们不难得出最大公约数的一些简单性质：例如任意改变的符号，不改变（）的值，即；（）可以交换，（）＝（）；（）作为的函数，以为周期，即对于任意的实数，有（）＝（）等等。为了更详细地介绍最大公约数，我们给出一些常用的一些性质：
（1）设是不全为0的整数，则存在整数，使得；
（2）（裴蜀定理）两个整数互素的充要条件是存在整数，使得；
事实上，条件的必要性是性质（1）的一个特例。反过来，若有使等式成立，不妨设，则，故及，于是，即，从而。
（3）若，则，即的任何一个公约数都是它们的最大公约数的约数；
（4）若，则；
（5）若，则，因此两个不互素的整数，可以自然地产生一对互素的整数；
（6）若，则，也就是说，与一个固定整数互素的整数集关于乘法封闭。并由此可以推出：若，对于有，进而有对有。
（7）设，若，则；
（8）设正整数之积是一个正整数的次方幂（），若（）＝1，则都是整数的次方幂。一般地，设正整数之积是一个正整数的次方幂（），若两两互素，则都是正整数的次方幂。
定义2.设是两个非零整数，一个同时为倍数的数称为它们的公倍数，的公倍数有无穷多个，这其中最小的一个称为的最小公倍数，记作，对于多个非零实数，可类似地定义它们的最小公倍数［］。
最小公倍数主要有以下几条性质：
（1）与的任一公倍数都是的倍数，对于多于两个数的情形，类似结论也成立；
（2）两个整数的最大公约数与最小公倍满足：（但请注意，这只限于两个整数的情形，对于多于两个整数的情形，类似结论不成立）；
（3）若两两互素，则［］＝｜｜；
（4）若，且两两互素，则｜。
典例分析
例1． 设是正整数，且，它们的最小公倍数是最大公约数的120倍，求。
解：设，则，其中且，于是。
所以即
由及（2）可得：
。
由（1）可知只能取
从而或29，故或。
例2．设，，则。
证明：设，则，，其中。
于是，已知条件转化为，
故更有，
从而转化为，
但是，
故，结合，
知必有，同时，因此。
例3．设正整数的最大公约数是1，并且，证明是一个完全平方数。
证明：设，则，，其中，由于，故，现在问题中的等式可以转化为 ①
由此可见整除。因为，故，同样可得，再由便可以推出。设，其中是一个正整数。一方面，显然整除；另一方面，结合①式，得，故，从而，但，故。
因此，，故，这样就证明了是一个完全平方数。
例4． 都是正整数，是否存在整数使得对任意的正整数，与互质？
解：令，，则，于是存在整数使得，
令，则对任意的正整数，设，有
即，而，，所以，即对任意的正整数，（，）＝1。
例5． 已知，证明：对于任意的正整数，都有两两互素。（2002年克罗地亚竞赛试题）
证明：设（其中出现次）。由，故对于有，则是含有0次项的多项式。因此，除以的余数为1。设整数可整除和，又＝，则当
除以
时余数为1，即
＝
＋1。所以
，矛盾！
从而可知
两两互素。
例6．求出所有的正整数对
，使得
是一个整数。（2006年山东省第二届夏令营试题）
解：由于
且
，所以
是对称的。不妨设
。
当
时，则
，从而＝2；
当
时，若
时，则有
，所以
或3；
若
时，由于是一个整数，从而
使得
即
，所以
＜
。
又由于，
，所以
。
所以
，
从而
得
或3，所以
；
综上知所有的为（2,2）,(2,1),(1,2),(3,1),(1,3),(5,2),(2,5),(5,3),(3,5).
例7．已知
，且
，试问
的充要条件是
分析：因为
，所以
；
又
，所以
；
令
，则有
又因为
，所以
从而上式
且
为奇数，即的充要条件是且
为奇数。
例8．我们知道
有1个质因子，且
；
有2个质因子，且
………………
如此下去，我们可以猜想：
至少有
个质因子，且
。试证明之。
证明：令
＝，则＝
，即要证
是整数且有
个质因子。下用数学归纳法证明是整数。
时，结论显然；
假设
时，成立；
当＋1时，因为
(－1)3+1=3－32＋3；
因为
，所以
，即
是整数。
下证至少有个质因子。
＝3－32＋3＝(
)3－3()2＋3().
因为＝(
)，令
，则＝
由于(,3)=1，所以(,)=1，从而必有异于质因子的质因子，
所以至少有个质因子。
