高二数学竞赛班二试数论讲义-同余4
高二数学竞赛班二试讲义
第4讲 同余与剩余类
班级 姓名
一、知识点金
1．同余
两个整数
除以正整数
，若余数相同，则称
与
关于模同余，
记作
，这叫做同余式。
2．性质
以下性质均在整数范围内讨论，模为正整数。
（1）若
，则当
时，；
则当
时，
。
（2）若
，
，且
，则
。
（3）费尔马小定理：
为素数，对任意正整数，都有
。
费尔马小定理的推论：设为素数，为正整数，且
，
。
证明：由于
模的余数各不相同，否则，若有
，其中
，则
，而不整除，所以
，这是不可能的，因此模的余数必然取遍
这
个数，仅可能顺序不同。
故
。
又为素数，则
，所以由性质（1）得。
3．剩余类
设
，把全体整数按对模的余数进行分类，余数为
的所有整数归为一类，记为
，称为模的一个剩余类
。
显然，是一个以为公差的无穷等差数集。它有如下性质：
（1）
，且
；（2）对任意
，有唯一的，使得
。
（3）对任意
，
。
4．完全剩余系
设
是模的全部剩余类，从每个任取一个数
，
这个数
组成的一个数组称为模的一个完全剩余系，简称完系。
称为模的最小非负完系。
二、例题分析
例1．（1）求证：
是正奇数时，
能被
整除。
（2）是自然数，它不能被
整除，求证：
与
中有且只有一个数被整除。
1
例2．
；
是
的两种不同排列。
求证：
中至少有两个被
除所得的余数相同。
例3．设三角形的三边长分别是整数
，且
。已知
，其中
，而
表示不超过
的最大整数，求这种三角形周长的最小值。
1
三、同步检测
1．计算
个
的乘积，则其最后三位数是（ ）
A．
B．
C．
D．
2．
被
除的余数是 。
3．求证：
为任意整数
。
4．求证：
1