整数的性质及其应用(2)
基础知识
最大公约数与最小公倍数是数论中的一个重要的概念，这里我们主要讨论两个整数互素、最大公约数、最小公倍数等基本概念与性质。
定义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－3
2＋3
；
因为
，所以
，即
是整数。
下证
至少有
个质因子。
＝
3－3
2＋3
＝(
)3－3(
)2＋3(
).
因为
＝
(
)，令
，则
＝
由于(
,3)=1，所以(
,
)=1，从而
必有异于
质因子的质因子，
所以
至少有
个质因子。