高二数学竞赛班二试数论讲义-同余4

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