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

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


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

? 欧拉函数 ? (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) 。矛盾表明结论成立!


更多相关文档:

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

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

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

初等数论中的几个重要定理初等数论中的几个重要定理隐藏>> 初等数论中的几个重要定理 基础知识 定义(欧拉(Euler)函数)一组数 定义 意的 对模 个数, , 的剩余...

初等数论定理

初等数论定理_数学_自然科学_专业资料。初等数论 1. 整除性质 a) b) c) d...初等数论(四)-几个著名的... 2页 1下载券 第五节初等数论中的几个......

初等数论

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

初等数论

纵观数论发展过 程,我国出现了许许多多的数论大师,...+1)便可得到 其中数学中的一个著名定理是:不可...在第一章第 6 节还指出了可以利用第 4 节中关于...

初等数论知识点汇总

初等数论知识点汇总_理学_高等教育_教育专区。个人收集第一节 整数的 p 进位制...面的问题中有着不可替代的功能, 与之密切相关的的数论定理有欧拉定理、 费尔...

初等数论总复习

为此在辅导材料的最后给大家介绍数 论中著名的“哥德巴赫猜想”和费马大定理的...四、自学指导 整除是初等数论中最基本的概念之一,b∣a 的意思是存在一个整数...

初等数论练习题答案

事实上,由?(8)=4,?(3)=2,?(5)=4 以及欧拉定理立得结论。 初等数论练习题三一、单项选择题 1、若 n>1,?(n)=n-1 是 n 为质数的( A.必要但非...

初等数论

定理 4.Pell 方程 最小解为 ,则它的全部解可以...初等数论中的几个重要定理基础知识 定义(欧拉(Euler...与之密切相关的的数论定理有欧拉定理、费尔马 定理...

《初等数论》教学大纲

《初等数论》教学大纲_理学_高等教育_教育专区。课程名称:初等数论(Elementary Number...4、欧拉定理、费马定理及对循环小数的应用 (1)欧拉定理;(2)费马定理;(3)...
更多相关标签:
网站地图

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