tceic.com
学霸学习网 这下你爽了
相关标签
当前位置:首页 >> 理学 >>

费马小定理和欧拉定理的应用


6

中 等 数 学

费马小定理和欧拉定理的应用
王连笑
( 天津市实验中学 , 300074) 中图分类号 : O 156 文献标识码 : A 文章编号 : 1005 - 6416( 2010) 11- 0006- 05

(本讲适合高中 ) 费马小定理和欧拉定理是数论中非常重 要的两个定理, 对解决整除问题和同余问题 有着强大的功能 , 因此 , 也是数学奥林匹克命 题的一个丰富宝藏. 与费马小定理和欧拉定 理有关的题目是国内外数学竞赛命题中出现 频率十分高的一类问题 . 本文先介绍与此有 关的一些知识, 所涉及的定理及结论可以在 任何一本数论书中找到证明 , 不再赘述, 然后 通过几个例题介绍这两个定理及有关知识的 应用. 1 基础知识 1 1 欧拉函数 ( 1) 欧拉函数 的数的个数 . , 例如, 1 = 1 ( 2) 欧拉函数 ( i) 欧拉 函数 a, b = 1 ,则 m m 的定义: m 表示 , m - 1 中与 m 互质 5 = 5 , 10 = 4 ( 与

T (m )

有正约数. 则
i= 1

d i = m.

例如, m = 12 , 其正 约数为 1 、 2 、3 、 4 、 6、 12 ,而
1 + 2 + 3 + 4 + 6 + 12

= 1+ 1+ 2+ 2+ 2+ 4= 12= m. 1 2 欧拉定理 对每个整数 n > 1 和一切与 n 互质的正 整数 a , 都有 a
(n)

1 m od n .

1 3 费马小定理 设 p 是质数. 若 ( a, p ) = 1 ,则 a 1 m od p . 1 4 威尔逊定理 设 p 是质数. 则 p - 1 ! 1 5 阶数和原根 ( 1) 定义 . 当 a, m = 1 时, 有最小正整数 使 a 1 m od m , 且 a
k p- 1

- 1 mod p .

对正整数 m, 数列 0 , 1 ,

10 互质的数为 1 、 3 、 7 、 9, 共 4 个 ). m 的性质. m 是 积性 函数 , 即 若 a
k k

1 m od m ( k = 1 , 2 ,

, - 1 ). m , | m .

则 称为 a 关于 m 的阶数. 由欧拉定理显然有 ! 如果 = m , 即 a 关 于 m 的阶 数是

ab =

b.
k- 1

( ii) 若 p 是质数 , 则 p = p- 1 , p =p -p . ( iii)设 m = p 1 1 p 22 p k k , 其中, p i ( i= 1 , 2 , , k) 为不同的质数 . 则 m = m 1( iv)设 d1, d2, 1 p1 11 p2 11 . pk

m , 则称 a 为 m 的原根 . 例如, a = 3 , m = 10 , 10 = 4 , 由于 3=3 , 3= 9 , 3 = 27 , 3 = 81 则 3 关于 10 的阶数是 原根. 又如, a = 3 ,m= 8 , 2 3 = 9 1 m od 8 , 8 = 4 , 由于
1 2 3 4

1 mod 10 ,

10 = 4 , 3 是 10 的

, dT (m ) 是正整数 m 的所

收稿日期 : 2010- 07- 28

则 2是 3 关于 8 的阶数, 而 3 不是 8的原根 .

2010 年第 11 期

7

因为任何奇数的平方关于模 8都与 1 同 余 , 所以, 8 的原根不存在 . ( 2) 性质 . 1 2 ( i) 如果 a 关于 m 的阶数是 , 则 a , a , ,a 中的任何两个数对 m 不同余 . ( ii) 若 是 a 关于 m 的阶数 , 则 a
t - 1

所以, 本题无解 . 例 3 证明 : 方程 x + 5= y 没有整数解. ( 1979 , 保加利亚数学奥林匹克 ) 证明 假设方程有整数解 x, y . ( 1) 当 x 为奇数时, 则 x + 5 2 m od 4 . 3 于是, y 2 m od 4 . 因此, y 是偶数 , 即 y 因而, y
3 2 2 3

1 m od m

| t.

2 例题选讲 例 1
2 2

0 m od 2 .

0 m od 4 , 矛盾 .

证明: 若 a, b = 1 , p 为质数 , 且

p | ( a + b ), 则 p - 1 m od 4 . 证明 用反证法 . 假设 p = 4k - 1( k N + ). 由 a, b = 1 , 则 a、 b 不可能都被 p 整除. ( 1)当 a 和 b 恰有一个能被 p 整除时, 不妨 设 p |a ,p b ,则p b ! p
2

( 2) 当 x 为偶数时, 设 x = 2n. 3 2 由 y = x + 5 1 mod 4 , 则 y 1 ( mod 4), 可设 y = 4m + 1 . 原方程化为 x + 4= y - 1 . 2 2 3 则 4 n + 1 = x + 4= y - 1 = y- 1 y + y+ 1
2 2 2 3

( a + b ), 矛盾.

2

2

( 2) 当 a 和 b 都不能被 p 整除时 , 由费马 小定理有 p- 1 p- 1 p | ( a - 1 ), p | ( b - 1 ). 故p| a - b ,即 p | a - b 4k - 2 4k - 2 又 p b, 则 p b ! p 2b . 于是, p a +b ,即 2 2 4k - 4 4k - 6 2 p a +b a +a b + 因此, p
2 4k - 2 4k - 2 p- 1 p-1 4k - 2 4k - 2

= 4 m 16 m + 12 m+ 3. 2 从而, n + 1= m d, 其中, d = 16 m + 12 m+ 3
2

- 1 ( mod 4).

.

所以, d 至少有一个质 因数是 4k - 1 型 2 ( 可由例 1 知 n + 1 不可能有 4k - 1 型的质 因数, 因此 , 无整数解 ). 设 p = 4l - 1是 d 的一个质因数. 则 2 n + 1= md 0 m od p , 即 n
2

+ b

4k - 4

.

( a + b ), 矛盾.
2

2

2

- 1 m od p .
p- 1 4l - 2 2 2l - 1

所以, a + b 没有 4k - 1 型的质因数. ?说明 #本题 表明两个互质的 平方数之 和的奇质因数一定是 4k + 1的形式 . 下面的两个例题是这一结论的应用. 例 2 在整数集里, 求 x 的解.
2 010 [ 1]

故 n = n = n - 1 m od p . n
p- 1

? %

另一方面, 由费马小定理知 1 m od p . 式 ? 与 % 矛盾. 此时 , 也无整数解. 所以, 方程没有整数解. ?说明 #本例给出的方程 x + 5= y 称为
2 3

- 2 006= 4y

2 009

+ 4y

2 008

+ 2 007y

( 2009 , 马其顿数学奥林匹克 ) 解
2 010

原方程化为
2 009 2 008

莫德尔方程 , 其基本形式是 2 3 y = x + k. 关于莫德尔方程有一些结果: ( 1 ) 费马指出, 他已经严格证明了 y = x - 2 y > 0 只有 3 , 5 一组解.
3 2

x + 1= 4y + 4y + 2 007y + 2 007 2 008 = 4y + 2 007 y + 1 . 由于 4y + 2 007 - 1 m od 4 , 则 4y + 2 007 必有 4k - 1 型的质因数.
2 008 2 008

( 2) 费马还指出 , y = x - 4 y > 0 只有 两组解 2 , 2, 5 , 11 , 但费马没给出证明. 2 3 ( 3) 欧拉证明了 y = x + 1 y > 0 只有

2

3

而 x, 1 = 1 ,则 x 的质因数, 矛盾.

2 010

+ 1 没有 4k - 1 型

8

中 等 数 学

2 , 3 一组解 , 但他的证明不完全 . 根据著 名的 图埃 & 莫 德尔 & 西 格尔 定 理 , 除非 k = 0 , 它最多只有有限组整数解 ( 即 有限多组解 , 平凡解或无解 ). 多数莫德尔方程具有整数解, 虽然只有 有限个 , 但能求出它的全部解也是很困难的 事 , 即使 k 很小. 对某个 k, 求出它的全部解, 有时是一篇论文的主题. 例如, 1954 年的一篇博士论文就是求莫 德尔方程 y = x + 17 y > 0 的全部整数解 ( x, y ) = - 1 , 4, - 2 , 3, 2 , 5, 4 , 9 , 8, 23 , 43 , 282 ,
2 3

由 于 2 011 2 011
2 011

2 011

<

10

4

2 011

= 10

8 044

, 则

至多有 8 044 位.
2 011

故 Q 2 011 ! 9 ? 8 044= 72 396 . 2 011 于是, Q 2 011 至多有 5 位, 有 Q Q 2 011 ! 9 ? 5= 45 . 2 011 从而, Q Q 2 011 至多 有 2 位 , 且
2 011

不大于 45 , 而不大于 45 的正 整数的各位数 码之和不大于 3+ 9= 12, 即 2 011 Q Q Q 2 011 ! 12. 又 Q Q Q 2 011
2 011 2 011

4 mod 9 , 则

Q Q Q 2 011 = 4 . 例 6 求所有的质数对 p, q , 使得 pq | 5 + 5 .
p q [ 2]

52 , 375 , 5 234 , 378 661 . 共八组解. n 例 4 证明: 数 列 2 - 3 中, 一 定有一 个任意两项互质的无穷子数列 . n 证明 设数列 2 - 3 中 , 已有 k 项是两 两互质的, 记为 u 1, u2, uk + 1 = 2 其中, 2
( u 1u2 uk ) + 1

( 2009 , 中国数学奥林匹克 ) 解 ( 1) 若 m in { p, q } = 2 , 不妨设 p = 2, 则要使 2q | 5 + 5 = 25+ 5 , 须使 q | 25+ 5 . q q 因为 5 + 25 = 5 - 5 + 30 , 所以 , 由费马 小定理得
q q | 5 - 5 ! q |30 . 此时, q = 2 , 3 , 5 . q 2 q q

, u k. 作 - 3 ,

x 是欧拉函数 .
( u1u 2 u k )

由欧拉定理得 = 2
( u 1 ) ( u2 ) ( uk )

当 q = 2 时, pq = 2 ? 2= 4 合要求 ;

5 + 5 ,不
2 3

2

2

1 ( m od u i ) ( 1! i! k ). 故 2
( u1u 2 u k ) + 1

- 3 , uk + 1 是 k + 1 项的
n

- 1 ( m od ui ) ( 1! i! k ). 所以, 数列 u1, u 2, 两两互质的子数列.

当 q = 3 时, p q = 2 ? 3 = 6 | 5 + 5 , 知 , 3 为一解 ; p, q = 2 当 q = 5 时, pq = 2 ? 5= 10 | 5 + 5 , 知 p, q = 2 , 5 为一解 .
2 5

依此下去, 在数列 2 - 3 中 , 一定有一 个任意两两互质的无穷子数列 . 例 5 设 Q n 表示正整数 n 的各位数 码之和 . 求 Q Q Q 2 011 解 4 4 显然, Q n
2 011 2 011 2 011

( 2) 若 m in { p, q} = 5 , 不妨设 p = 5 , 要使 5q | 5 + 5 , 须使 q | 5 + 625 . 5 5 当 q = 5 时, pq = 5 ? 5= 25 | 5 + 5 , 知 p, q = 5 , 5 为一解 .
q- 1 5 q q- 1

.
2 011

n m od 9 . m od 9 .

则 2 011

= 9 ? 223+ 4

当 q ( 5 时, q | ( 5 + 625 ), 又由费马小 q- 1 定理有 q | 5 - 1 , 则 q | 626! q = 313 . 下面验证 p, q = 5, 313 符合要求. 注意到 p q = 5 ? 313 | 5 + 5
5 5 313 4 312 313

= 4
6

6 ? 335+ 1

由欧拉定理得
( 9)

= 4

1 m od 9 4 m od 9 4 m od 9 .

,
312

! 2 0112 011

! Q Q Q 2 0112 011

5 + 5 = 5 5 + 5 = 5 5 - 1+ 626 . 312 因为 313 | ( 5 - 1+ 626 ), 所以 ,

2010 年第 11 期

9
5 313

pq = 5 ? 313 | 5 + 5

,

因此, 对任意的 n > 1 , n n ( 2 - 1 ).
n n

N + , 都有

知 p, q = 5 , 313 为一解. ( 3 ) 若 m in { p, q } > 5 , 则 要 使 pq | p q p- 1 q- 1 5+ 5 = 5 5 + 5 , 从而 , pq | 5
p-1

?说明 #若 a > 2 , 则存在无穷多个正整数 n, 使得 n | ( a - 1). 下面用数学归纳法构造一个无穷递增的 正整数数列 nk 满足 : nk | ( a k - 1 ).
n

+5

q- 1

.

? % ) N + ).

由费马小定理有 p-1 5 1 m od p . 由式 ? 、 %得 5 - 1 m od p . k 设 p - 1= 2 2r - 1 , q - 1= 2 2 s - 1 ( k、 、 l r 、 s 若 k ! l, 则由式 % 、 )得 1 1
2 l- k ( 2s- 1) l q- 1

( 1) 当 k = 1 时 , 取 n 1 = 1 , 满足条件. ( 2) 假设对某个 k
n n n q

N+ , 有 nk | ( a k - 1), N + ). 于是 ,
n

n

则取 nk + 1 = a k - 1= nk q ( q = nk + 1M (M 所以, nk + 1 | ( a
n

a k + 1 - 1= a k - 1= a k - 1 M N + ).
nk + 1

5

p-1

2l- k ( 2s - 1 )

- 1).

5 2l ( 2s - 1 ) ( 2r - 1) 5 - 1 即
2r - 1

2k ( 2r - 1 )? 2l - k ( 2s- 1)

于是, 若 a > 2 , 则存在无穷多个正整数 5
q- 1 2r - 1

n, 使得 n | ( a - 1). 例 8 设 m 是正整数 . 如果 2 除 3 + 1 , 证明 : 2 证明 3
2m 2m m+ 1 m+1

- 1 m od p ,

+ 1整

2 0 m od p . 这与 p ( 2 矛盾 . 同理, 当 k + l 时, 矛盾. 此时, 不存在符合要求的质数对 p, q . 综上及 p、 q 的对称性得 , 满足题目要求

+ 1是质数 . + 1 .由 q| 3 + 1,则 ? - 1
2 2m

( 2003 , 韩国数学奥林匹克 ) 设 q= 2
m+ 1

- 1 m od q .
2m 2

故 3 , q = 1 . 由式 ? 得 3 m od q , 即 % 3 2
2m + 1

的质数对 p, q = 共七组解. 例 7 证明 : 对任意的 n > 1 , n 有 n ( 2 - 1 ). 证明 用反证法 . 假设存在某个正整数 n > 1 , 使得 n n | ( 2 - 1 ). 因为 2 - 1是奇数 , 所以 , n 是奇数 . 设 p 是 n 的最小质因数 . 则 (p, 2) = 1, ( n, p - 1 ) = 1 . 由费马小定理有 p | ( 2
p- 1 n n

2 , 3, 3 , 2 , 2, 5 , 5 , 2, 5 , 5, 5 , 313 , 313 , 5. N+ , 都

1 m od q . = q- 1 .

由式 ? 、 % 易知 3 关于 q 的阶数为
m+ 1

另一方面, 由欧拉定理知 m+ 1 2 = ( q - 1) | q . 由于 则 q ! q - 1, 而由式 ) , 有 q = q- 1 .
m+ 1

)

q +q - 1 , 因而, q 是质数 , 即 2 + 1 是质数 .

练习题
1. 若将一个数各个数位上的数码颠倒后 仍得到原数 , 则称这个数为 , 回文数 ?. 证明 : 等差数列 18 , 37 , 中包含无数个回文数 . ( 2009 , 新加坡数学奥林匹克 ) 提示: 见 .中等数学 / 2010 年增刊 ( 二 ), 第 72页 .

- 1 ).

设 d 是 2关于 n 的阶数, 即 m d = m in m p | ( 2 - 1 ), m N+ . 则 d | (p - 1), d | n. 又 n, p - 1 = 1 , 则 d= 1 . d 1 此时, p | ( 2 - 1 ) = 2 - 1= 1 , 矛盾 .

10

中 等 数 学

2 . 求最小的正整数 m, 使得 2 009 |m, 且 m 在十进制表示中数字和等于 2 009 . ( 2009 , 塞尔维亚数学奥林匹克 ) 提示: 见 .中等数学 / 2010 年增刊 (二 ), 第 105页 . 3 . 设正整数 a、 b 使 15a + 16b 和 16a - 15b 都是正整数的平方. 求这两个平方数中较小 的数能够取到的最小值.
[ 3]

整数 N 可表示为 N = A n + 6 ? 10 ( 0 ! k ! n).
k n- 1

这里, A n =

i= 0

10 .

i

显然, 当 3 | n 时 , N 是合数. 当 3 n 时, 由费马小定理有 6 10 1 m od 7 . 又 10 - 1 ( mod 7 ), 故 10 关于 7 的阶 数为 6 . 从而,
s- 1 3

( 1996 , 中国数学奥林匹克 ) 2 2 提示: 设 15a + 16b = r , 16a - 15b = s ( r、 s N + ). 消去 a 得 2 2 481b = 16r - 15s ! 481 | ( 16r2 - 15 s2 ). 由式 ? 得 2 2 16r 15s m od 13 . 若 13
12

An =
i- 0

10 ( m od 7), 3 , 6 ( m od 6 ). r 0 mod 7 .

i

其中, s n 因此, A n ? %

于是, 当 n > 6时 , 必存在一个 k 使得 k 6 ? 10 7- r m od 7 ! N 0 m od 7 . 所以, N 不是质数. 而当 n = 4 , 5 时, 1 711= 29 ? 59 , 11 711= 7 ? 1 673 . 所以, 只有 n = 1 , 2时 , N 是质数. 2 n 5. 若正整数 n( n > 1 ), 满足 n | ( 2 + 1 ), 证明: 3 | n . 提示: 设 p 是 n 的 最 小 质 因 数. 则 由 2+ 1 是奇数 , 有 p + 3. 设 2关于 p 的阶数是 l. 则 l ? 2 1 m od p . 2 n 又 n | ( 2 + 1 ), 及 p |n, 则 n 2n 2 - 1 m od p , 2 1 m od p . % 由费马小定理得 p- 1 2 1 m od p . ) 由式 ? 、 %、 ) 及阶数的定义有 l | 2n, l | (p - 1). 又 n, p - 1 = 1 , 则 2n, p - 1 = 2 . 于是, l= 2 . l 2 从而, p | ( 2 - 1 ) = 2 - 1= 3. 考虑到 p 是质数, 则 p = 3 . 于是, 3 |n.
n

r , 13

s, 则由费马小定理得

s 1 mod 13 . 由式 % 得 16r s 15 s 15 2 m od 13 . 5 12 2 10 6 6 则 4rs = 16r s 2 = 64 - 1 m od 13 . 这与费马小定理矛盾 . 所以, 13 | r, 13 | s . 类似证明: 37 | r, 37 | s(略 ). , 则 481 | r, 481 | s. 又 13 , 37 = 1 2 2 2 2 于是, r + 481 , s + 481 . 由 r - s = 15a + 16b - 16a - 15b = - a + 31b, 则当 a = 481 ? 31 , b = 481 时, r = s = 481 . 于是, 所求的最小值是 481 . 4 . 试求所有的正整数 n, 使得 n - 1 个数 码 1 与一个数码 7 构成的每一个十进制表示 的正整数都是质数. (第 31届 I M O 预选题 ) 提示: 显然, n = 1 , 2 满足条件 . 下面证明: n + 3 不满足条件. 由 n - 1 个 1 与一个 7 构成的每一个正
2 2 2 2 2 2 2 10 12

参考 文献 :
[ 1] [ 2] [ 3] 2009 马其顿数学奥林 匹克 [ J] . 李 学 , 2010增刊 ( 二 ) . 2009中国数学奥林匹克 [ J] . 中等数学 , 2009 ( 3) . 1996中国数学奥林匹克 [ J] . 中等数学 , 1996 ( 2) . 翚 译 . 中等数


推荐相关:

浅论费马小定理

11 长江师范学院本科毕业论文·费马小定理及其在素性检验中的应用研究 引 言...如欧拉的证明方法等; 对费马小定理的应 用研究一直以来也是数学家们的追求,如...


费马小定理

因此将整个 公式除以 W 即得到: 广义 费马小定理欧拉定理的一个特殊情况:...在后面我们讲到费马小定理的应用时, 我们更能从很多实际例子体会到它的威力。 ...


费马小定理

费马小定理_数学_高中教育_教育专区。欧拉定理和费马小定理 欧拉定理和费马小定理的证明: 欧拉定理的证明: 若 a 1, a2 ,?, a?? m? 跑遍模 m 的简化剩余...


同余及其应用

同余及其应用 CONGRUENCE AND ITS APPLICATIONS 专姓指导教 业:信息与计算科学 ...本文还研究 了一些特殊的同余式,如威尔逊定理和费马小定理、伪素数、欧拉定理。...


浅谈同余及其应用

剩余类 与剩余系、欧拉定理费马小定理、循环小数、一次同余方程及一次同余方程...故 r=2. 分析: 此类题目解题的关键在于应用同余的乘方性, 先求出底数 20102...


11数论的几个重要定理

11 数论的几个重要定理欧拉定理费马小定理、威尔逊定理及中国剩余定理是数论的四大定理,它们是解决 数论问题的重要工具。下面介绍这几个定理在竞赛数学中的应用方法...


费马定理、欧拉定理、威尔逊定理(讲稿)_图文

费马定理欧拉定理、威尔逊定理(讲稿)_数学_高中教育_教育专区。2014希望联盟...应用:设(a, m)=1, c 是使得 ac≡1(mod m)的最小正整数, 则 c|φ(...


欧拉函数

欧拉函数_计算机软件应用_IT/计算机_专业资料。φ 函数的值 通式: φ (x)...(2-1)=24 与欧拉定理费马小定理的关系 对任何两个互质的正整数 a, m, ...


RSA算法数学原理_计算机软件及应用_IT/计算机_专业资料

RSA算法数学原理_计算机软件应用_IT/计算机_专业资料。RSA算法数学原理整理 ...因为质数 p 的φ(p)等于 p-1,则欧拉定理可以写成 这就是著名的费马小定理...


数论重要定理

一、欧拉定理 的整数, 设 m > 1 的整数, ( a...( mod 从而有1 ≤ r 五、阶及应用 定理 1 设...则 r / 2n. 又由小费马定理知, 2 ∴r p ?1...

网站首页 | 网站地图
All rights reserved Powered by 学霸学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com