当前位置:首页 >> 学科竞赛 >> 初等数论(四)-几个著名的数论定理

初等数论(四)-几个著名的数论定理


初等数论(四)--几个著名的数论定理
一些常用概念

? 欧拉函数 ? (n) --介于 1 和 n 之间与 n 互质的自然数个数 ? 缩系---在 ? (n) 个剩余类中各取一个元素,它们形成一个模 n 的缩系
问题: 为什么要介绍缩系这个概念呢?这是因为当我们定一个缩系后, 剩余类中的其它元素 均可以由缩系生成。设 (a, m) ? 1

,则有 s , t 使得

as ? mt ? 1 。
任取一个不是缩系中的元素 b ,就有

b ? asb ? mtb
从而有

b ? asb(mod m) 。
即, b 可以表成 ka(mod m) 的形式(即,由 a 的若干倍生成) ,从而凡是与 b 有关的数论问 题(在模 m 的意义下可以转化为 a 的问题) 。这就是群论中的生成元的问题。在高中里面的 复数理论中也是如此。 下面这个结果表明了一种构造缩系的方法: 例 1. 设 (m, n) ? 1 。如果 {a1 , a2 ,..., at },{b1, b2 ,..., bs } 分别是模 m 和模 n 的缩系,那么

S ? {mbi ? na j 1 ? i ? s,1 ? j ? t}
就是模 mn 的缩系。 解答:第一步。先证明 S 中每一个元素都与 mn 互质。这是显然的。 第二步。证明 S 任意两个数关于模 mn 不同余。假定有某两个数 mbi ? na j 与 mbi ? na j 关于
' '

模 mn 同余,

mbi ? na j ? mbi' ? na'j (mod mn)
则必有 m(bi ? bi ) ? n(a j ? a j )(mod mn) 。从而有
' '

(bi ? bi' ) ? 0(mod n),(ai ? ai' ) ? 0(mod m) ,
即有 bi ? bi , a j ? a j ,矛盾!
' '

第三步。证明:如果一个数 c 与 mn 互质,那么必然与 S 中某个元素关于模 mn 同余。 由于 (m, n) ? 1, 方程 mx ? c(mod n) 在模 n 剩余类中有解;由于 (c, n) ? 1, 所以 ( x, n) ? 1。 因此, x 与某个 bi 在模 n 的同一个剩余类中,即有

mbi ? c(mod n);
同理有 a j 使得

na j ? c(mod m)
自然有

mbi ? na j ? c(mod n); mbi ? na j ? c(mod m).
根据 (m, n) ? 1,

mbi ? na j ? c(mod mn)
这就网完成了证明。 例 2.在 1, 2,3,..., pa 中有多少个数与 p a 互质? 解答:在 1, 2,3,..., pa 中不与 p a 互质的数有形式 kp,1 ? k ? pa ?1 。所以

? ( p a ) ? p a ? p a ?1 ? p a ?1 ? ? 。 p
? ?
如果自然数 n ? p1 1 p2 2 ... pk k , 那么
? ? ?

?

1?

? (n) ? n ?1 ?
?

?

? 1? ? 1 ? 1 ? ? ? ?1 ? ? ? ... ? ?1 ? ? p1 ? ? p2 ? ? pk ?

关于 ? (n) 还有其他表达方式:

? (n) ? n ? ?1 ? ? 。 p
pn p质数

? ?

1? ?

注意:大家可以尝试用容斥原理来证明这个公式。 下面介绍著名的费马小定理
? (m)

例 2.设 m 是一个自然数, (a,m)=1 。证明: a

? 1( mod m) 。这就是著名的欧拉定理。

如果取 m ? p 为质数,那么就成为了费马小定理。 证明:设 x1 ,x2 ,...,xt (t=? (m)) 是一个模 m 的缩系。那么

ax1 , ax2 ,..., axt

中任何两个都与 m 互质,其中没有两个相同。从而它也是一个缩系,在模 m 的意义下,

ax1 , ax2 ,..., axt 仅仅是 x1 ,x2 ,...,xt 的一个置换。从而有 ax1ax2 ...axt ? x1 x2 ...xt (mod m) 。
证明完毕。 例 3.证明:任意的 2 p ? 1 个整数中一定可以选出 p 个数,它们的和可以被 p 整除,这里 p 是一个质数。 证明:反证法。如果 a1 , a2 ,..., a2 p?1 中任意 p 个数 ai , ai ,..., ai 的和都不是 p 的倍数,那么 1 2 p 由费马小定理有

(ai1 ? ai2 ? ... ? aip ) p ?1 ? 1(mod p) 。
注意到形如上式的组合共有 C2 p ?1 个,对所有这样可能的组合求和后得到;
p

?
因为 C2pp ?1 ? ?

(ai1 ? ai2 ? ... ? aip ) p?1 ? C2pp ?1 (mod p)

? 2 p ? 1? ? ? 1(mod p) 。 ? p ?

l 1 ?2 ai2 ...ai? (l ? p ?1) 的 项 。 在 (ai1 ? ai2 ? ... ? aip ) p ?1 展 开 后 得 到 形 如 ai? 1 l

?

中含有

?l l 1 ?2 ai? ai2 ...ai? (l ? p ?1) 的项有 C2pp ?1?l 个(即,从 ai1 , ai2 ,..., ai p 以外的书中取 p ? l 个与它搭 1 l

配成形如 ai , ai ,..., ai 的组合) 。注意到 C2 p ?l ?1 ? 1 2 p

p ?l

(2 p ? 1 ? l )(2 p ? l )...( p ? 1) p 被 p 整除, ( p ? l )!

因此上面和式左边 ? 0(mod p) 。矛盾表明结论成立!


更多相关文档:

初等数论(四)-几个著名的数论定理

初等数论(四)-几个著名的数论定理_学科竞赛_高中教育_教育专区。初等数论(四)--几个著名的数论定理一些常用概念 ? 欧拉函数 ? (n) --介于 1 和 n 之间与...

初等数论中的几个重要定理

初等数论中的几个重要定理 基础知识 定义 (欧拉(Euler)函数) 一组数 且对于...特别地, ,当 程组.若整数 同时满足: ,则剩余类 解,写作 定理4: (中国...

第五节初等数论中的几个重要定理

第五节初等数论中的几个重要定理_学科竞赛_高中教育_教育专区。第五节基础知识 初等数论中的几个重要定理 定义(欧拉 (Euler)函数)一组数 x1 , x2 ,?, xs ...

第五节初等数论中的几个重要定理

第五节基础知识 初等数论中的几个重要定理 定义(欧拉(Euler)函数)一组数 x1 , x 2 ,L , x s 称为是模 m 的既约剩余系,如果对任意的 定义 1 ≤ j ...

初等数论中的几个重要定理

4页 2财富值如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 初等数论中的几个重要定理 隐藏>> 初等数论中的几个重要...

初等数论中的几个重要定理(竞赛必备)

初等数论中的几个重要定理 基础知识 定义(欧拉(Euler)函数)一组数 的, 的...初等数论(四)-几个著名的... 2页 1下载券 ©2015 Baidu 使用百度前必读 ...

初等数论

数论四大定理 ? 费马小定理:初等数论本讲内容: ? 数论基本性质 ? 同余及同余...(China reminder theory) 1、整除的概念 2、公约数 3、公倍数 4、欧几里得...

初等数论中的几个重要定理

初等数论中的几个重要定理初等数论中的几个重要定理隐藏>> 初等数论中的几个重要...(中国剩余定理) 中国剩余定理 定理 4:(中国剩余定理)设 方程组 , 均为 的...

100个著名初等数论问题

100个著名初等数论问题_数学_自然科学_专业资料。100 个著名初等数学问题 http:...第 25 题 阿贝尔不可能性定理 Abel's Impossibility Theorem 高于四次的方程...

初等数论中的几个重要定理

初等数论中的几个重要定理 基础知识 定义(欧拉(Euler)函数)一组数 的模, 的...则剩余类 余方程组的一个解,写作 (其中 )称为同 定理 4:(中国剩余定理)设...
更多相关标签:
初等数论四大定理 | 初等数论 之孙子定理 | 初等数论 | 初等数论 pdf | 初等数论第三版答案 | 初等数论 潘承洞 | 初等数论及其应用 | 初等数论难题集 |
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com