初等数论第三章课件

一、同余的概念及其主要内容基本性质 二、剩余类及完全剩余系 第三章 同余 三、简化剩余系与欧拉函数 四、欧拉定理、费马定理及其应用 第一节 同余的概念及其基本性质 数论中有它自己的代数，称之为同余理论。它既有 重要的理论价值，又具有广泛的实际应用价值。 人们在 生活、生产、宗教、习俗及民间游戏中，常会遇到已日 数计时、天文历法计算等问题。因而，简化数据，保留 精神实质就成其当务之急，于是，产生了数论中的一些 重要概念。 , (m o d ) , (m o d ) mm a b a b m a b m a b m a b m 定 义 给 定 一 个 正 整 数 ， 把 它 叫 做 模 。 如 果 用 去 除 任 意 两 个 整 数 所 得 的 余 数 相 同 ， 我 们 就 说 对 模 同 余 ， 记 作 ， 如 果 余 数 不 同 ， 我 们 就 说 对 模 不 同 余 ， 记 作 。 1, , ab m m a b a b mtt Z 定 理 整 数 对 模 同 余 的 充 分 与 必 要 条 件 是 即 。 1 1 2 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 , , , ( m o d ) = ) ; , ) ( ) , ,= a m q r b m q r r r m a b m r r a b m q q m a b m m q q r r m r r r r m r r 证 ： 设 ,0 若 ， 则 ， 因 此 （ 若 则 （ ,因 此 但 故 。 1 ,m a b ab m 注 ： （ 1） 由 定 理 ， 可 得 到 同 余 的 另 外 一 个 定 义 ： 即 若 则 叫 做 对 模 同 余 。 1 (mod )a b m a a b mt （ 2） 由 定 理 说 明 ， 等 价 于 可 表 示 为 1 0(mod ), , ma a m mm （ 3） 定 理 推 论 ， 该 推 论 说 明 在 模 的 同 余 关 系 中 的 倍 数 可 用 零 来 代 替 。 1, , ab m m a b a b mtt Z 定 理 整 数 对 模 同 余 的 充 分 与 必 要 条 件 是 即 。 1 ( m o d ) 2 ( m o d ) , ( m o d ) 3 ( m o d ) , ( m o d ) ( m o d ) a a m a b m b a m a b m b c m a c m 同 余 的 基 本 性 质 （ ） （ ） 则 （ ） ， 则 1 1 2 2 1 2 1 2 ( 4 ) (m o d ), (m o d ) (m o d ); (m o d ), (m o d ) a b m a b m a a b b m a b c m a c b m 若 ， 则 若 则 1 1 2 2 1 2 1 2 ( 4 ) (m o d ), (m o d ) (m o d ); (m o d ), (m o d ) a b m a b m a a b b m a b m ak bk m 若 ， 则 若 则 11 11 11 11 11 11 1 0 1 0 5 ( m o d ) , ( m o d ) , 1 , 2 , , ( m o d ) ( m o d ) , 0 , 1 , , , ( m o d ) kk kk kk kk ii kk ii n n n n n n n n A B m x y m i k A x x B y y m a b m i n a x a x a b x b x b m （ ） 若 则 ； 特 别 地 ， 若 则 11 11 (6) (mod ), , ,( , )1 (mod ) a b m a adb bd dm a b m 若 且 ， 则 ( 7 ) ( m o d ) , 0 , ( m o d ) ( m o d ) , , , , 0 m o d a b m k a k b k m k a b m d a bm d a b m d d d 若 则 若 ， 则 12 (8) (m od ), 1,2, , , (m od , , , ) i k a b m i k a b m m m 若 则 (9 ) (m o d ), , 0 , (m o d ) a b m d m d a b d 若 则 (10) (mod ), ( , ) ( , ) , a b m am bm d m a b d ab 若 则 ， 因 而 若 能 整 除 及 ， 两 数 之 一 ， 则 必 能 整 除 中 的 另 一 个 。 4061 3 9例、求 写成十进位数时的个位数。（） 2 ( ) ( )(mod )p p pp ab a b p 例、设 是素数，证明 。 11() p p p i p i i p p p p pa b a C a b C a b C b 证 ： 根 据 二 项 式 定 理 有 ： 1,2, , 1 ,( !, ) 1 !( 1) ( 1) ,iipp i p i p i p p i C pq pC 当 时 ， 故 即 ( 1) ( 1) ! ! ( 1) ( 1) i p p p p i CZ i i p p p i 3 1 2 1 7 2 2 +1 7 n n n n 例 、 （ ） 求 所 有 的 正 整 数 ， 使 得 能 被 整 除 ； （ ） 证 明 ： 对 于 任 何 正 整 数 ， 不 能 被 整 除 。 3 3 3 1 , 3 , , 0 ,1,2 . 2 1(m o d 7 ) 2 1(m o d 7 ) 2 1 0 (m o d 7 ), 3 ,7 2 1 mm n n Z m k m N k nm 解 ： （ ） 都 可 写 成 的 形 式 其 中 因 为 ， 所 以 ， 即 从 而 当 ； 3 1 3 22 2 (m o d 7 ) 2 4 (m o d 7 ), 3 ,7 2 1 mm nnm 又 ， 从 而 当 且 仅 当 时 .3 3 1 3 22 1 2(mod7)2 1 3(mod7),2 1 5(mod7), ,2 1 7 m m m nn （ 2） 由 ， 可 知 ， 对 任 何 正 整 数 不 能 被 整 除 . 4 4 ,1 2 3 4 5n n n nn n 例 、证明当且仅当 不能被 整除时 能被 整除，其中 是正整数。 4 4 4 4 1 2 3 4 1 1(mod5), 2 16 1(mod5),3 81 1(mod5),4 256 1(mod5), n n n n nS 证 ： 不 妨 设 ， 容 易 验 证 , 4 44 4 , 0 ,1 , 2 , 3 . 1 (m o d 5 ), 1 , 2 , 3 , 4 . 1 (m o d 5 ), (m o d 5 )k n k r r k r r aa a a a a 假 定 其 中 由 以 上 知 则 有 所 以 1 2 3 4 1 2 3 4 (m o d 5 ). 0 ,1 , 2 , 3 4 4 (m o d 5 ) 1 0 0 (m o d 5 ) 3 0 0 (m o d 5 ) 1 0 0 0 (m o d 5 ) 4 1 2 3 4 5 . n n n n r r r r n n n n n n n n n S rS S S S n 因 此 可 得 因 而 当 时 ， 依 次 有 ， ， ， ， 故 当 且 仅 当 不 能 被 整 除 时 ， 能 被 整 除 2 2 25 x y z例、证明方程 没有都是素数的解. 2 2 2 , , , 2 ( )( ) 4 5 4 , 1 2 x a y b z c a c b a c b c b c b c b c 证 ： （ 反 证 法 ） 设 是 素 数 解 如 果 ， 由 得 ， 因 此 ， 从 而 ， 矛 盾 。 22 2 2 2 , 1 ( m o d 4 ) 1 ( m o d 4 ) 2 ( m o d 4 ) ab ab a b c 于 是 都 是 奇 数 。 因 此 ， ， 但 ， 矛 盾 。 同余的一个应用 检查因数的一些方法 1 10 , 10 10 ,0 10.nnn n i a Z a a a a a a 证 ： 将 写 成 十 进 位 数 的 形 式 ： A、一整数能被 3（ 9）整除的充要条件是它的十进位 数码的和能被 3（ 9）整除。 1 1 1 1 0 1(m o d 3 ), 1 0 1(m o d 3 ), 1 0 (m o d 3 ), 1 0 (m o d 3 ), (m o d 3 ). ii ii n n n i i i i i i i aa a a a a 因 故 从 而 即 11 3 3 3 . nn ii ii a a a a 得 到 ， 由 此 当 且 仅 当 1 9 9 . n i i aa 同 法 可 得 当 且 仅 当 Ba给出7（11或13）整除的充分与必要条件。 第二节 剩余类及完全剩余系 由带余数除法我们知道，对于给定的正整数 m，可以 将所有的整数按照被 m除的余数分成 m类。 本节将对此作 进一步的研究。 0 1 1 1 , , , , ( 0 ,1 , , 1 ) ( 0 , 1 , 2 , ) mr m m K K K K r m qm r q 定 理 若 是 一 个 给 定 的 正 整 数 ， 则 全 部 整 数 可 分 成 个 集 合 ， 记 作 其 中 是 一 切 形 如 的 整 数 所 组 成 ， 这 些 集 合 具 有 下 列 性 质 ： (i)每一整数必包含在且仅在上述的一个集合里面， (ii)两个整数同在一个集合的充要条件是这两个整数 对模 m同余 0 1 1 0 1 1 11 1 , , , , , , , m m m K K K m a a a m a a m 定 义 定 理 中 的 叫 做 模 的 剩 余 类 ， 一 个 剩 余 类 中 任 一 数 叫 做 它 同 类 的 数 的 剩 余 . 若 是 个 整 数 ， 并 且 其 中 任 何 两 数 都 不 同 在 一 个 剩 余 类 里 ， 则 叫 做 模 的 一 个 完 全 剩 余 系 . 推论： m个整数做成模 m的一个完全剩余系的充要条 件是两两对模 m不同余 0,1, , 1,m m 注：最常见的完全剩余系是 它们 称为模 的非负最小完全剩余系 . 下面例 1给出模 m的另外完全剩余系 绝对最小完 全剩余系 . , , 1 , , 1 , 0 , 1 , , 1 ; ( 1 ) 2 2 2 1 , 1 , , 1 , 0 , 1 , , ( 2 ) 2 2 2 . m m m m m m m m 例 1 当 是 偶 数 时 及 都 是 模 的 完 全 剩 余 系, -1 -1 -1 , 1 , , 1 , 0 ,1 , , (3 ) 2 2 2 . m m m m m 当 是 奇 数 时 是 模 的 完 全 剩 余 系 0 1 1 0 1 1 2 ( , ) 1 m , , , , , , m m m a m b x a x b m a a a m a a b a a b a a b m 定 理 设 是 正 整 数 ， ， 是 正 整 数 ， 若 通 过 模 的 一 个 完 全 剩 余 系 ， 则 也 通 过 模 的 完 全 剩 余 系 ， 也 就 是 说 ， 若 是 模 的 完 全 剩 余 系 ， 则 也 是 模 的 完 全 剩 余 系 . 1 2 1 2 1 2 2 1 1 2 12 3 , , , , . m m xx m m m x m x mm 定 理 若 是 互 质 的 两 个 正 整 数 而 分 别 通 过 的 完 全 剩 余 系 ， 则 通 过 模 的 完 全 剩 余 系 1 1 1 1 0 31 2 1 , , 1 , 0 , 1 , , 31 3 3 3 1 , 0 1 n nn nn i H H H x x x x x n H 例 、 （ ） 证 明 中 每 一 个 整 数 有 而 且 只 有 一 种 方 法 表 示 成 的 形 状 ， 其 中 或 . (2) 说 明 应 用 +1 个 特 制 的 砝 码 ， 在 天 平 上 可 以 量 出 1 到 中 的 任 何 一 个 斤 数 . 1 1 1 31 1 , , 1 , 0 , 1 , , 31 2 1 2 1 31 2 1 3 . 31 n n n H H H HH HH （ ） 证 : 首 先 包 含 个 不 同 的 整 数 ， 是 模 的 绝 对 最 小 完 全 剩 余 系 ， 且 由 得 1 11 1 3 3 3nn nn n x x x x 其 次 ， 要 证 明 也 是 模 3 =2H+1的 绝 对 最 小 完 全 剩 余 系 。 （ 再 由 模 2H+1 的 绝 对 最 小 完 全 剩 余 系 具 有 唯 一 性 得 到 结 论 ） 1 1 1 0 11 1 1 0 3 3 3 1 1, 0 ,1( 0 ,1, , 1) 3 3 3 3 3 3 nn nn i ii n n n nn x x x x n x i n x x x x x 共 有 项 ， 当 时 ， 每 一 项 各 取 个 值 ， 故 共 通 过 个 数 ； 1 1 1 0 1 1 0 1 0 0 1 1 1 1 0 0 0 0 3 3 3 3 = 3 3 3 3 ( ) 3 ( ) 3 ( ) 3 n n n n n n n n n nn n n n n x x x x x x x x x x x x x x x x x x x x 在 这 个 数 中 ， 若 有 则 12 1 1 1 1 1 1 1 1 22 +1 3 ( ) 3 ( ) ( ) = 0 3= = 3 nn n n n n nn n x x x x x x x x x x x x x x 从 而 同 理 ， ， ， 即 此 个 数 中 ， 两 两 互 不 相 同 ； +1 1 1 1 1 1 1 0 3 13 3 3 1 13 3 3 1 3 3 3 , 21 n n nn nn nn nn H H x x x x H H H 此 个 数 中 ， 最 大 值 为 3 最 小 值 为 -3 即 通 过 中 的 个 整 数 ， 结 论 成 立 。 2 2 1 1 , 3 , 3 , , 3 . . n n 解 ： （ ） 特 制 个 砝 码 分 别 重 斤 将 要 称 的 物 体 放 在 天 平 的 左 托 盘 ， 将 若 干 个 砝 码 放 在 右 托 盘 ， 为 达 到 平 衡 ， 可 以 在 左 托 盘 放 上 若 干 砝 码 1 11 1, 11 3 3 3 ii i nn nn xx x T x x x x 这 时 左 托 盘 里 的 砝 码 取 右 托 盘 里 的 砝 码 取 ， 由 （ ） 知 ， 当 取 适 当 的 值 时 ， 可 使 之 值 为 所 要 称 的 物 体 的 斤 数 。 第三节 简化剩余系与欧拉函数 0 1 11, , , , , , , (mod ) ( , ) ( , ). mr r m K K K K a K a r m am rm 对 模 有 个 剩 余 类 在 中 , . mm m 1、定义：如果一个模 的剩余类里面的数与 互质 就把它叫做一个与模 互质的剩余类 15 15 6 , , , ( , 6 ) (1 , 6 ) 1 , ( , 6 ) ( 5 , 6 ) 1 , ( , ) 1 . m a K K a a a m K K 例 当 时 有 若 即 此 时 的 与 ， 有 0 ,1 , , 1 m mm 注 ： 由 定 义 ， 要 找 出 所 有 与 模 互 质 的 剩 余 类 ， 只 需 找 出 序 列 中 所 有 与 互 质 的 数 即 可 得 到 ， 而 与 模 互 质 的 数 的 个 数 则 可 通 过 欧 拉 函 数 来 计 算 。 () 0 , 1 , , 1 a aa a 2 、 定 义 ： 欧 拉 函 数 是 定 义 在 正 整 数 上 的 函 数 ， 它 在 正 整 数 上 的 值 等 于 序 列 中 与 互 质 的 数 的 个 数 . , ( ) 1.m p p p 注：当 时 m m 3、 定 义 ： 在 与 模 互 质 的 全 部 剩 余 类 中 ， 从 每 一 类 各 取 一 数 所 作 成 的 数 的 集 合 ， 叫 做 模 的 一 个 简 化 剩 余 系 . 1 2 ( ) 1 2 ( ) 2 , , , ( ) , , , . m m a a a m m m a a a m 定 理 、 若 是 个 与 模 互 质 的 整 数 ， 并 且 两 两 对 模 不 同 余 ， 则 是 模 的 一 个 简 化 剩 余 系 4,8,16,28,32,44,52,56 15例：判定 是否为模的简化剩余系？ 4、简化剩余系的判定定理 8 4 4 , 8 8 , 1 6 1 , 2 8 1 3 , 3 2 2 , 4 4 1 4 , 5 2 7 , 5 6 1 1 ( m o d 1 5 ) , 15 解 ： 此 序 列 包 含 (15)= 个 数 ， 而 均 与 模 互 质 ， 并 且 两 两 不 同 余 ， 故 可 作 成 模 15 的 一 个 简 化 剩 余 系 . 5 2 ( ,) 1, , . am x m ax m 、定理 ：若 通过模 的简化剩余系 则 通过 的简化剩余系 1 2 1 2 1 2 2 1 12 1 2 6 4 , , , + . m m x x m m m x m x m m 、 定 理 ： 若 是 两 个 互 质 的 正 整 数 ， ， 分 别 通 过 模 的 简 化 剩 余 系 则 通 过 的 简 化 剩 余 系 1 2 1 2 2 1 1 2 1 2 12 ( ) ( ) ( )m m m m m x m x m m mm 分 析 ： 若 要 根 据 简 化 剩 余 系 的 条 件 来 判 定 ， 则 要 讨 论 与 的 数 量 关 系 ， 但 此 为 未 知 关 系 ， 故 问 题 转 换 为 证 明 通 过 模 的 一 个 完 全 剩 余 系 中 一 切 与 模 互 质 的 整 数 即 可 。 1 2 1 2 1 2 2 1 1 2 12 , , , ( , ) 1, 1 x x m m m m m x m x mm 证 ： 若 分 别 通 过 模 的 完 全 剩 余 系 则 （ ） 通 过 的 完 全 剩 余 系 . 1 1 2 2 1 2 1 2 2 1 1 2 1 1 2 1 1 2 2 1 2 2 1 1 2 1 2 1 ( , ) 1 , ( , ) 1 , 1 ( ) 1 ( + ) 1 ( + ) 1 ( + ) 1 x m x m x x m m m x m m x m x m m x m x m m x m x m m 在 （ ） 中 ， 若 即 集 合 （ ） 中 的 ， 通 过 模 ， 的 简 化 剩 余 系 ， 则 ， ， ， 同 理 ， ， 2 1 1 2 2 1 1 2 1 2 1 1 2 2 1 2 1 2 + ( + ) 1 ( , ) 1,( , ) 1, m x m x m x m x m m x m x m x x m m 反 之 ， 在 中 ， 若 ， ， 则 即 ， 通 过 模 ， 的 简 化 剩 余 系 . 1 2 1 2 1 2( , ) 1 ( ) ( )( )mm mm m m 推论：若 ，则12 12 12 7 5 , 1 1 1 ( ) 1 1 1 k k k a p p p aa p p p 、 定 理 ： 设 则 1212() kka p p p 证： 1,2 1,2 p p p p p p p p 等 于 从 减 去 ， ， 中 与 不 互 质 的 数 的 个 数 ， 亦 等 于 从 减 去 ， ， 中 与 不 互 质 （ 即 被 整 除 ） 的 数 的 个 数 . 11,2 ,pp p p p 而 ， ， 中 被 整 除 的 数 的 个 数 是 1=.p p p 故 1 1 2 2 1111 1 2 2 12 () 1 1 1 1 1 1 kk kk k a p p p p p p a p p p 由 、 得 8、下面给出欧拉函数的一些性质 1= 2=1, 3 2mm （ ） （ ） 当 时， （ ） ( ) ( )nm n m ( ) ( ) ( , ) ( ) ()d m nmn d mn d 当 时 ， 有 ( , ) 11 11 1 ( ) 1 1 1 p m p n p m n p m n pp m n m n m n p p 证 ： ( , ) 11 11 ( , ) 1 1 ( , ) p m p n p m n mn pp mn m n p ( ) ( ) ( ) ( ) 1 () () m n d m n dd d ( ) ( )2nn n n n n ， 当 为 合 数 时 ， 1 ( 4 ) 2 ( ) ( ) 2 2 ( ) 2 3 , 3 1 6 , ( ) 3 k kl nZ n n n n n n k Z n n n k l Z n n n 例 、 设 ， 证 明 ： 若 是 奇 数 ， 则 的 充 要 条 件 是 ， 的 充 要 条 件 是 ， 若 则 (4 ) (4) ( ) 2 ( )n n n 证： 111( ) 2 , (2 ) 2 1 2 22 k k k knn 若 则 11 1 11 1 1 1 ( ) ( )11 2 22 ( ) , 1 2 k k nn nn nn n n n n 所 以 ， 即 11 1 1 1 1 1 ( ) , 2 , 2 1 ( ) ( 2 ) ( 2 ) ( ) 2 ( ) 2 k k k k n n n n n n n n n n （ ） 若 设 为 奇 数 . 则 由 ( ) 2 3 , ( 2 ) (3 ) 1 1 1 2 1 3 1 2 3 3 k l k l kl nn n 若 则 ( )= 11 1 1 1 1 1 1 1 ( ) , 2 3 , ( 6 , 3 ()11 ( ) ( 2 ) ( 3 ) ( ) 33 ( ) , 1 , 2 3 kl kl kl n n n n n n n n n n n n n n n （ ） 若 设 )=1. 则 由 即 11 11 1 2 3 , ( 6 , 1 ( ) ( 2 ) ( 3 ) ( ) 2 3 ( ) 3 11 23 33 kl k l k l kl n n n n n n nn 设 )=1. 则 由 ( , ) 1 1 22 1 () 2 1 1 , 2 , , ( ) 2 in in n i n n n n n n 例 、 设 整 数 ， 证 明 ： 即 在 数 列 中 ， 与 互 质 的 整 数 之 和 为 1 2 ( ) 1 2 ( ) , , , ( , ) 1 1 1 1 ( ) n i i n n n a a a a n a n in 证 ： 设 在 ， ， ， 中 与 互 质 的 个 数 是 ： ， ， ， ， ( m o d ) ( , ) ( , ) 1 1 1 , 1 ( ) i i i i i n a a n n a n a n n a n i n 则 由 得 ， 并 且 ， 1 2 ( ) 1 2 ( ) 1 2 ( ) 1 2 ( ) , , , , , , n n nn a a a n a n a n a a a a n a n a n a 因 此 ， 集 合 与 集 合 是 相 同 的 ， 于 是 1 2 ( ) 1 2 ( ) 2 ( ) 1 () 2 n n a a a n n a a a n n 3 ( ) (1) ( ) ( ) ( ) ( ) da i p p p ii d a 例 、 证 明 ： 21 ( ) (1) ( ) ( ) 1 1) ) )kk k i p p p p p p p p 证 ： （ （ （ 12 12 12 12 12 12 00 ( ) , ,0 () k k ik k ik k k i i k da ii a p p p d p p p d p p p 证 法 一 ： 设 则 所 以 1212 00 ik k ik kp p p 11 12 11 12 0 0 0 kk kk kk kkp p p p 1 12 1 12 0 0 0 i k k k i k k kp p p 11 11 11 11 0 0 0 kk kk kk kkp p p 1212 kkp p p a 1 2 ( ) 1 2 ( ) , , , , , , ( ) ( ) Ta Ta d a d a d d d a a a a a d d d a d d 证 法 二 ： 若 是 的 所 有 正 因 数 ， 则 也 是 的 所 有 正 因 数 ， 于 是 1,2 , , , , (1) . ja aa 我 们 来 把 正 整 数 按 其 与 的 最 大 公 因 数 分 类 ， 即 与 的 最 大 公 因 数 相 同 的 作 为 一 类 1 2 3 4 6 1 2 1 2 , 1,5 ,7 ,1 1 , 2 ,1 0 , 3,9 , 4 ,8 6 , 1 2 da T a d T T T T T T 例 如 ： 表 示 与 的 最 大 公 因 数 为 的 数 的 集 合 ， 则 ， d每一个正因数 对应于一个类，这些类两两不相交， 且并集为集合（ 1） ( , ) ,1 ( 2 ) 2 ( , 1 1 ( ) 2 . j a d j a aa j d h h h dd a hj d 我 们 来 求 这 些 子 集 ： 设 ， （ ） 式 就 等 价 于 ） ， ， 而 这 样 的 的 个 数 为 ， 这 也 就 是 满 足 式 （ ） 的 的 个 数 ( ) ( ) d a d a a ad d 因 而 由 以 上 讨 论 知 第四节 欧拉定理、费马定理及应用 m m 模 的 简 化 剩 余 系 可 以 取 种 种 不 同 的 形 式 ， 但 每 个 简 化 剩 余 系 中 所 有 数 的 乘 积 对 模 是 同 余 的 ， 1 ( ) 1 ( ), , , , ,1 , ( ) mm ij r r r r m k Z r r km i j m 即 若 ； 以 及 都 是 模 的 简 化 剩 余 系 ， 那 么 存 在 ， 使 ， 则 1 ( ) 1 ( ) (m o d ) 3 . mmr r r r m Fermat Euler 由 此 及 第 三 节 定 理 就 可 推 出 著 名 的 定 理 () 1 1( ) 1 ( , ) 1 1(mod )m Euler m am am 、 定 理 设 是 大 于 的 整 数 ， ， 则 2 ( ) (mod )p Fermat p a a p 、 推 论 小 定 理 当 是 素 数 时 ， ( ) 1 ( , ) 1 1(m o d ) 1(m o d ) (m o d ) pp p a p Euler a p a p a a p 证 ： 若 ， 由 定 理 有 ， 即 ， 因 而 ( , ) 1 0(m od ) , (m od ) p p a p p a a a p p a Z a a p 若 ， 则 ， 此 时 ， 综 上 所 述 ， 当 为 素 数 时 ， 对 19561 13 ?(mod60)例 、求 (13,60) 1, (60) (5 12) 16, 1956 16 122 4 解 ： (60) 16 1956 16 122 4 4 2 13 13 1(m od 60) 13 13 1 13 ( 11) 1(m od 60) 由 欧 拉 定 理 得 10102例 、 如 果 今 天 是 星 期 一 ， 问 从 今 天 起 再 过 10 天 是 星 期 几 ？ 7610,7=1 = =10 1mod7), （）解：（ ），（7）6，10 （ 10 10 (0 6), 10 6 10 (m od 6) r r q r r r 先 求 使 ， 即 求 ， 使 1 0 1 0 5 51 0 ( 2 ) 4 ( 2 ) 3 2 4 ( m o d 6 ) , 10 10 10 6 4 4 4 10 10 10 10 3 81 4(m od 7), 10 . q 故 再 过 天 是 星 期 五 2 1010 10 10 3 +10 + +10 例 、 如 果 今 天 是 星 期 一 ， 问 从 今 天 起 第 10 天 是 星 期 几 ？ 2 1010 10 10 (7 ) 6 +10 + +10 (10,7 ) 1, 10 10 1(m od 7 ) 解 ： 设 s=10 6 , 6 , 1 0 1 0 1 0 (m o d 7 )n q r r n Z n q r 故 对 设 必 有 10 ,10 ?(mod6)kkn下面计算当 时 2 32 4 5 1 0 1 0 4 (m o d 6 ), 1 0 4 (m o d 6 ), 1 0 1 0 1 0 4 4 4 (m o d 6 ), 1 0 1 0 1 0 4 (m o d 6 ) 同 理 有 4 4 4 5 5 2 1 0 1 0 1 0 1 0 1 0 3 2 3 5 ( m o d 7 ) . s 故 有 由 此 得 知 那 一 天 是 星 期 五 12 1 2 1 2 4 , , , , ( ) (m o d ) ) a p p p p aa p h h h Z h h h h h h p ii 例 、 (i) 证 明 ： 若 是 素 数 ， 则 （ 利 用 （ i) 证 明 费 马 小 定 理 ， 再 用 费 马 小 定 理 证 明 欧 拉 定 理 . 1 2 1 2 1 2 1 2 () ( ) (m o d ) (m o d ) . p aa p p p aa i h h h h h h p h h h h h h p 证 法 一 ： 由 费 马 小 定 理 得 及 故 结 论 成 立 1 2 1 2 1 1 1 1 11 () 2 ) ( m o d ) 1 ( ) ( ) ( m o d ) p p p p p p n n n n p p p an i a h h h h p a n a n h h h h h h h h h p 证 法 二 ： （ 数 学 归 纳 法 ） 当 时 ， 已 证 （ 成 立 ； 假 设 时 命 题 成 立 ， 那 么 当 时 ， 12( ) 1, (m od ) . p aii h h h a a p 取 即 得 ， 费 马 小 定 理 得 证 1 () ( , ) 1 1 (m o d ) 1 (m o d ) p p a p F erm at a p ap 下 面 证 明 欧 拉 定 理 ： 当 时 ， 由 小 定 理 得 即 () 1(mod ) 1pap下面用数学归纳法证 （） ( ) ( ) 1 1(m od ) 1 ,kkp k p k k a p a qp q Z 当 时 ， 已 证 成 立 ； 假 设 时 成 立 ， 即 ， 则 1 1 1 1 ( ) ( ) ( ) ) ( ) ) ( ) (1 )k k k k k k k k k p p p p p k p p p p p p p p p a a a qp 此 时 由 （ （ 得 1 ( ) 1 1 (1 ) (1 ) (1 ) 1 1 ( m o d ) 1 k k p i p p k p k k q p C i p p q Z a q p q p p 在 的 展 开 式 中 ， 系 数 是 的 倍 数 ， 故 ， 使 得 （ ） 式 获 证 12 12 () ( , ) 1, ( , ) ( , ) 1, 1 (m o d ) ( ) ( ) ki i ii i k i i p i i a m m p p p a p a p ap pm 设 得 从 而 有 ， 再 结 合 可 得 () 1(mod )im iap 1() 1 () ( , ) 1 , 1 , 1 ( m o d , , ) 1 ( m o d ) ji k ij m k m p p i j k a p p am 又 ， 所 以 即 1 1 1 0 0 1 1 01 01 5 2 0 1 1 4, () : ( 1 ) , , , ( 2 ) ( 2 ) , , , ( ) ( ) ( ) ( ) nn n n k k nn f x x a x a x a a a a m k k r r r f m f r f r f r 例 、 （ 年 全 国 数 学 联 合 竞 赛 加 试 题 ） 证 明 ： 对 任 意 整 数 存 在 一 个 次 多 项 式 具 有 如 下 性 质 均 为 正 整 数 ； 对 任 意 正 整 数 ， 及 任 意 个 互 不 相 同 的 正 整 数 ， 均 有 ( ) ( 1)( 2) ( ) 2f x x x x n 证 明 ： 令 ( ) 1fx n 将 的 右 边 展 开 即 知 是 一 个 首 项 系 数 为 的 正 整 数 系 数 的 次 多 项 式 。 ( ) (2)fx下面证明 满足性质 4 1, 2 , , 4 ( ) 2 (m o d 4 ) x n n x x x n fx 对 任 意 整 数 ， 由 于 ， 故 连 续 的 个 整 数 中 必 有 一 个 为 的 倍 数 ， 从 而 由 知 12 12 ( 2) , , , ( )( ) ( ) 2 0(m od 4) k k k k k r r r f r f r f r 因 此 ， 对 任 意 个 正 整 数 ， 有 12 ( ) 2(m od 4) ( ) ( )( ) () (m od 4)k m f m f m f r f r f r 但 对 任 意 正 整 数 ， 有 ， 故 12() ()() () ()kfm frfr fr fx从而 ，所以 符合题设要求. 欧拉定理的应用 小数与分数的互化 2 ,0 ( , ) 1 ( ,10) 1 a a b a b b b 定 理 、 有 理 数 ， 能 表 成 纯 循 环 小 数 的 充 要 条 件 是 11 0 1 , 0. tt a b a b a a a a a b 证 ： （ 必 要 性 ） 若 能 表 成 纯 循 环 小 数 ， 因 为 所 以 设 12 1 2 1 1 1 0 1 0 1 0 0 . , t t t t t t a a a a a a a a b a q q Z b 则 , (1 0 1 ) , ( , ) 1 1 0 1 (1 0 1 ) 1 0 1 ( m o d ) (1 0 , ) (1 0 , 1 ) 1 (1 0 , ) 1 t t tt tt aq a b q a b b bb bb 故 即 由 即 得 ， 从 而 ， 推 出 ， 即 ( ) ( , 1 0 ) 1 , 1 0 1 ( m o d ) , 0 ( ) 1 0 , 1 0 1 0 1 0 ( 1 ) 1 0 1 t t t t t i i b tZ b t b a q b a a q bb （ 充 分 性 ） ： 若 ， 则 由 欧 拉 定 理 得 ， 存 在 使 得 成 立 ， 因 此 且 1 1 2 1 1 1 1 11 1 0 , = 1 0 , 1 0 , , 1 0 0 9 , = 1 0 1 0 1 0 t t t t t tt i t t t aa q bb q q a q q a q q a a q q a a a 故 且 令 ， 则 ， 12 12 12 0 1 0 1 0 , , , , 9 0. 0 . , 10 1 0. 10 t tt tt t t q q a a a q a a a aa a a a bb 由 ， 即 得 且 不 全 是 ， 也 不 全 是 因 此 1 2 1 20. tt a a a a a a a b 反 复 应 用 上 式 即 得 1 1 1 3 0 , ( , ) 1 , 2 5 , ( , 1 0 ) 1 , 1 , , m a x , a a b a b b a b b b b b 定 理 、 若 是 有 理 数 ， 其 中 不 全 为 零 ， 则 可 以 表 成 混 循 环 小 数 ， 其 中 不 循 环 的 位 数 是