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

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


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

? 欧拉函数 ? (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: (中国...

初等数论

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

“初等数论初步”简介

算术基本定理初等数论的基石,它表明素数是正整数最...同余理论中蕴含大量的数论所特有的思想、概念和方法,...修四、径隅五”的 著名论断,它实际上给出了一个...

初等数论课程教学大纲新

初等数论课程教学大纲新_理学_高等教育_教育专区。《初等数论》课程教学大纲一、...3、了解 Fermat 小定理,熟练运用之。 4、理解中国剩余定理,掌握中国剩余定理的...

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

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

初等数论课程教学大纲

初等数论是研究整数的基本性质和 方程(组)整数解的一个数学分支。 数学与应用...简化剩余系 第四节 Euler 定理和 Fermat 定理 本章重点:剩余系的判定,欧拉...

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

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

初等数论

初等数论的大部份内容早在古希腊欧几里德的《 几何原本》中就已出现。欧几里得...4、带余除法定理: 设 a,b 是两个整数,其中 b>0,则存在两个唯一的整数 q...

初等数论论文

摘要:初等数论是研究数的规律,及整数性质的数学分支,它是数论的一个最古老的分支...定理 4 (1) 若 { r1 , r2 ,..., rm } 是模 m 的完全剩余系 , (...

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

第五节基础知识 初等数论中的几个重要定理 定义(欧拉(Euler)函数)一组数 x1 , x 2 ,L , x s 称为是模 m 的既约剩余系,如果对任意的 定义 1 ≤ j ...
更多相关标签:
初等数论四大定理 | 初等数论定理大全 | 初等数论欧拉定理 | 初等数论 | 初等数论第三版答案 | 初等数论 pdf | 初等数论 潘承洞 | 初等数论难题集 |
网站地图

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