高一联赛班春季班第12讲初等数论——费马小定理与阶

数论中有很多重要的定理，其中我们最为熟悉的就是费尔马小定理与孙子定理了.根据联赛大纲，

孙子定理只在冬令营中考到，因此本联赛班讲义不准备涉及到孙子定理.本讲将重点研究费马小定理.

从费尔马小定理出发，我们还将研究与它有很大联系的一个数论中新的工具：阶.

阶的概念在联赛大纲中并未明确提及，但是不论在联赛中还是冬令营乃至IMO 中，与阶相联系的问题都比比皆是.

完系与最小非负完系：

在m 个模m 的剩余类中各任取一个数作为代表，这样的m 个数称为模m 的一个完全剩余系，简称完系.

例如：0,1,...,1m -是模m 的一个完系，这称作模m 的最小非负完系．

缩系与欧拉函数：

如果i 与m 互素，则同余类i M 中所有数都与m 互素，这样的同余类称为模m 的缩同余类. 模m 的缩同余类的个数记作()m ϕ，称为欧拉函数. 在()m ϕ个缩同余类中各取一数为代表，这样的()m ϕ个数称为模m 的一个缩剩余系，简称缩系.

显然，(1)1ϕ=，而对1m >，()m ϕ为1,2,...,1m -中与m 互素的数的个数， 特别地，对素数p ，有()1p p ϕ=-.

欧拉函数可以如下计算：

第12讲 初等数论 费马小定理与阶

12.1费马小定理

设12

12k k m p p p ααα=⋅⋅⋅为m 的标准分解形式，则

111

()(1)...(1)k

m m p p ϕ=-

- 此定理的证明较复杂，且远远超出了联赛要求，故略去.有兴趣同学可自行参考相关书籍.

显然，当(,)1m n =时，有()()()mn m n ϕϕϕ=.

完系与缩系的几个重要性质： 当(,)1a m =，b 为任意整数时：

⑴若12,,...,m c c c 是模m 的完系，那么12,,...,m ac b ac b ac b +++也是模m 的完系. ⑵若12(),,...,m r r r ϕ是模m 的缩系，那么12(),,...,m ar ar ar ϕ也是模m 的缩系.

欧拉定理与费马小定理：

欧拉定理：设(,)1a m =，则()1(mod )m a m ϕ≡．

费马小定理：设p 是素数，p a Œ，则11(mod )p a p -≡．

费马小定理的另一形式：设p 是素数，则对任意整数a ，有(mod )p a a p ≡． (|p a 时，上式两端同余0；p a Œ时，上式等价于费马小定理的上一形式) 阶：

设1m >是一个固定的整数，(,)1a m =，可以证明，存在整数(1)k k m ≤<，使得1(mod )k a m ≡，我们将具有这一性质的最小正整数k 称为a 模m 的阶.它具有极其锐利的性质：

⑴设(,)1a m =，k 是a 模m 的阶，,u v 是任意整数，则(mod )(mod )u v a a m u v k ≡⇔≡，

特别地，1(mod )|u a m k u ≡⇔；

⑵设(,)1a m =，k 是a 模m 的阶，则数列23,,,...a a a 模m 呈周期出现，且最小正周期为k . 数列前k 项模m 互不同余；

⑶设(,)1a m =，k 是a 模m 的阶，则|()k m ϕ，特别地，a 模素数p 的阶整除1p -．

事实上，我们在以前的很多题中都运用到了阶的思想，只不过是没有明确提出.

但是，确定a 模m 的阶通常是极为困难的，逐一计算23,,,...a a a 模m 的余数可以求得阶，利用上述的性质（3），可以使这一过程稍微加快一些.

【例1】 试证明上面给出的完系与缩系的两个性质:

当(,)1a m =，b 为任意整数时，

若12,,...,m c c c 是模m 的完系，那么12,,...,m ac b ac b ac b +++也是模m 的完系.

若12(),,...,m r r r ϕ是模m 的缩系，那么12(),,...,m ar ar ar ϕ也是模m 的缩系.

【例2】 试设法证明欧拉定理及费马小定理.

【例3】 设1m >是一个固定的整数，(,)1a m =，证明：存在整数(1)k k m ≤<，使得1(mod )k a m ≡．

【例4】 设a 和m 都是正整数，1a >.证明：(1)m m a ϕ-.

【例5】 求证： 742|n n -

【例6】 设p 是奇素数，证明：21p -的任一素因子具有形式21px +，其中x 是正整数.

【例7】 设正整数a 与10互素，求20a （在十进制中）的末两位数码.

【例8】 将顺序为1,2,,2n 的2n 张牌变成1,1,2,2,,1,2,

n n n n n ++-，即原先的前n 张牌移至第2,4,,2n 张，这称为一次洗牌.试确定有哪些n ，从顺序1,2,,2n 开始，经过若干次洗牌可以恢复到原来状况.

【例9】 设*,m n N ∈，且m 为奇数，(,21)1n m -=.证明：(12)n n n m m +++.

【例10】 数列{}n a 定义如下：

2361(1,2,3,...)n n n n a n =++-=.

求与此数列的每一项都互质的所有正整数.

【演练1】求证：任何数的末位数与该数的五次方的末位数字相同；

实战演练

【演练2】设p 是奇素数，证明：21p +的素因子或者是3，或者具有形式21px +（x 是正整数）.

【演练3】设n 为一个正奇数，证明：存在一个各数码都为奇数的正整数m ，使得n m .

【演练4】设1,n n >∈*N ，证明：|(21)/

n n -．

【演练5】设a 和n 为整数，均不等于1±，且(,)1a n =，证明：至多有有限个k ，使得|(1)k k n a -．

细说：全国高联和初联竞赛大纲

细说：全国高联和初联竞赛大纲 一、初中数学竞赛大纲 1、数 整数及进位制表示法，整除性及其判定；素数和合数，最大公约数与最小公倍数；奇数和偶数，奇偶性分析；带余除法和利用余数分类；完全平方数；因数分解的表示法，约数个数的计算；有理数的概念及表示法，无理数，实数，有理数和实数四则运算的封闭性。 2、代数式 综合除法、余式定理；因式分解；拆项、添项、配方、待定系数法；对称式和轮换对称式；整式、分工、根式的恒等变形；恒等式的证明。 3、方程和不等式 含字母系数的一元一次方程、一元二次方程的解法，一元二次方程根的分布；含绝对值的一元一次方程、一元二次方程的解法；含字母系数的一元一次不等式的解法，一元二次不等式的解法；含绝对值的一元一次不等式；简单的多元方程组；简单的不定方程（组）。 4、函数 二次函数在给定区间上的最值，简单分工函数的最值；含字母系数的二次函数。 5、几何 三角形中的边角之间的不等关系；面积及等积变换；三角形中的边角之间的不等关系；面积及等积变换；三角形的心（内心、外心、垂心、重心）及其性质；相似形的概念和性质；圆，四点共圆，圆幂定理；四种命题及其关系。 6、逻辑推理问题 抽屉原理及其简单应用；简单的组合问题简单的逻辑推理问题，反证法；极端原理的简单应用；枚举法及其简单应用。 二、高中数学竞赛大纲 全国高中数学联赛（一试）所涉及的知识范围不超出教育部2000

年《全日制普通高级中学数学教学大纲》中所规定的教学要求和内容，但在方法的要求上有所提高。 全国高中数学联赛加试 全国高中数学联赛加试（二试）与国际数学奥林匹克接轨，在知识方面有所扩展；适当增加一些教学大纲之外的内容，所增加的内容是： 1.平面几何 几个重要定理：梅涅劳斯定理、塞瓦定理、托勒密定理、西姆松定理。三角形中的几个特殊点：旁心、费马点，欧拉线。几何不等式。几何极值问题。几何中的变换：对称、平移、旋转。圆的幂和根轴。面积方法，复数方法，向量方法，解析几何方法。 2.代数 周期函数，带绝对值的函数。三角公式，三角恒等式，三角方程，三角不等式，反三角函数。递归，递归数列及其性质，一阶、二阶线性常系数递归数列的通项公式。 第二数学归纳法。平均值不等式，柯西不等式，排序不等式，切比雪夫不等式，一元凸函数。 复数及其指数形式、三角形式，欧拉公式，棣莫弗定理，单位根。多项式的除法定理、因式分解定理，多项式的相等，整系数多项式的有理根*，多项式的插值公式*。 n次多项式根的个数，根与系数的关系，实系数多项式虚根成对定理。 函数迭代，简单的函数方程* 3.初等数论 同余，欧几里得除法，裴蜀定理，完全剩余类，二次剩余，不定方程和方程组，高斯函数[x]，费马小定理，格点及其性质，无穷递降法，欧拉定理*，孙子定理*。 4.组合问题 圆排列，有重复元素的排列与组合，组合恒等式。组合计数，组合几何。抽屉原理。容斥原理。极端原理。图论问题。集合的划分。