费马小定理及应用

费马小定理及应用知识定位费马小定理是初中数学竞赛数论中常常出现的一种。要熟练掌握费马小定理是数论中的一个定理，数学表达形式和应用。本节我们通过一些实例的求解，旨在介绍数学竞赛中不定方程相关问题的常见题型及其求解方法本讲将通过例题来说明这些方法的运用。 知识梳理1、欧拉函数：φ(m)是 1, 2, …, m 中与 m 互质的个数，称为欧拉函数.① 欧拉函数值的计算公式：若 m＝…, 则 φ(m)＝m (1－)(1－)…(1－)例如，30＝2·3·5，则ϕ(30)=30(1−12 )(1−13 )(1−15 )=8. ② 若 p 为素数，则若 p 为合数，则③ 不超过 n 且与 n 互质的所有正整数的和为；④ 若 若⑤ 设 d 为 n 的正约数，则不大于 n 且与 n 有最大公因数 d 的正整数个数为，同时；2、欧拉定理：若(a, m)＝1，则 aφ(m)≡1(mod m).证明：设 r1，r2，…，rφ(m)是模 m 的简化剩余系，又 (a, m)＝1，∴a·r1，a·r2，…，a·rφ(m)是模 m 的简化剩余系，∴a·r1×a·r2×…×a·rφ(m)≡r1×r2×…×rφ(m)(mod m)，又 (r1·r2·…·rφ(m), m)＝1，∴aφ(m)≡1(mod m).应用：设(a, m)＝1, c 是使得 ac≡1(mod m)的最小正整数, 则 c|φ(m).补充：设 m＞1 是一个固定的整数, a 是与 m 互质的整数，则存在整数 k (1≤k≤m)，使ak≡1(mod m)，我们称具有这一性质的最小正整数(仍记为 k)称为 a 模 m 的阶，由 a 模 m 的阶的定义，可得如下性质：（1）设(a, m)＝1，k 是 a 模 m 的阶，u, v 是任意整数，则 au≡av (mod m)的充要条件是 u ≡v (mod k)，特别地，au≡1 (mod m)的充要条件是 k|u证明：充分性显然.必要性：设，由及知.用带余除法，故，∴，由的定义知，必须，所以（2）设(a, m)＝1，k 是 a 模 m 的阶，则数列 a, a2, …, ak, ak＋1,…是模 m 的周期数列，最小正周期为 k，而 k 个数 a, a2,…, ak 模 m 互不同余.（3）设(a, m)＝1，k 是 a 模 m 的阶，则 k|φ(m)，特别地，若 m 是素数 p，则 a 模 p 的阶整除 p－1.（4）设(a, p)＝1, 则 d0是 a 对于模 p 的阶≡1(mod p), 且 1, a, …, ado−1对模 p两两不同余.特别地, do＝φ(p)⇔ 1, a,…, aφ(p)−1构成模 p 的一个简化剩余系.定理：若l 为a 对模m 的阶，s 为某一正整数，满足as≡1(mod m)，则s 必为l 的倍数.3、费尔马小定理若 p 是素数，则...