nbhkdz.com冰点文库

高中数学奥赛系列辅导材料 数论函数


上教考资源网
高中数学奥赛系列辅导材料 数论函数
【内容综述】 本讲介绍数论中常见的一些函数的概念、性质及其应用,主要有 除数函数 ——自然数 n 的正因数的个数函数; ——自然数 n 的全部正因数的和函数; 欧拉函数 号“ ”: ; ——设 n 是大于 1 的自然数,则欧拉函数

助您教考无忧

是表示与 n 互素且不

大于 n 的自然数的

个数;(高斯函数或称方括号函数[X]在下讲介绍)为书写清楚,同学们应熟悉连加符号“ ”与连乘符

特别是“ “ 【要点讲解】

”表示对称式的和 ”表示对称式的积 abc??;



§1.约数个数函数 §2.约数和函数 §3.欧拉函数 φ (n) ★ §1. 约数个数函数 定义 1 定理 1 设 设 ,则 的正约数的个数称为函数 ,且 是质数 , 。 则 ★ ★

略证: 由乘法原理,约数系由



、?、

的不同取法而生成,它们的取法分别有 种(含不取该约数的 1 种取法),故得证

例 1. 求 24 的正约数个数。 解:

事实上,易求得约数分别是 1,2,3,4,6,8,12,24;个数正是 8 个。 §2 约数和函数 定义 定理 2 设 。 自然数 的正约数和函数 , ,则称 的

正约数和为函数

(其中

为 的素数,

) 。

版权所有@中国教育考试资源网

上教考资源网
略证 注意到( )

助您教考无忧

, 展开后,其项数恰为 的约数个数 , 又每项皆形如 , ,于是有

可见每项皆自然数 的约数且每个约数只出现一次,由此可见该积即

例 2. 求 780 的正约数和 解:



定理 3

若 、 是互质的自然数,即(a,b)=1,则

证明: 设 ∵ ,故





与 各不相同(i=1,2,…,j=1,2,…,m)

§3.欧拉函数 定义 设 如 每个小于 的自然数都与它互素) ;反之可见,若 是合数,必有 关于欧拉函数 ,有以下性质定理 则 互素的充要条件是 ,即有: ,反之若
版权所有@中国教育考试资源网

互素且不大于 的自然数的个数( ),称为欧拉函数。 ,易证 是素数 。 (∵

定理4 设 P 是素数,且

证明 ∵P 是素数,显然有 与

上教考资源网
,且知在 1 和 之间,有以下 个数是 p 的倍数: ,而其余的数都与 互素,从而可知不超过

助您教考无忧
且与 互素的自然数个数。

当自然数 的素因数分解式中,不只包含一个素因数时,有 定理 5 设大于 1 的自然数的素因数分解式为 , 其中 则有

证明: 因为素因数的个数 (i)当

, 故考虑采用数学归纳法 (下设 ;

表有 k 个素因数的自然数 ) 。

(ii)设 注意到加入第个 k+1 素因数 后,有 , 且当 于是由归纳假设就有



从而

时,定理成立;

版权所有@中国教育考试资源网

上教考资源网

助您教考无忧

综上,对任意 (★的补证: 引理 设 、 、c∈N,则 (i)若 , 从而 可见 故 同理可证 (ii)若 ,则存在素因数 ,由 则

同理,若 再证定理 若 ,则 (★★) 注意到 到 的自然数排成长 ,故 中有一个数为 1 时, (★★)显然成立,现假设 并把从 1 方阵:

1 m+1 2m+1

2 m+2 2m+2

?? ?? ?? ??

r m+r 2m+r

?? ?? ??

m 2m 3m

(n-1)m+1

(n-1)m+2

??

(n-1)m+r

nm

则 的自然数个数。

为上面这组数中与 注意到(km+r,m)=(r,m), 所以当

互素的自然数的个数, 由引理知它等于这组数中同时与

都互素

时,第 列中的每一个数都与 列的每列数中,恰好有

互素,从而这 个自然数与

列数中共有

列数与



素。 下面再证这 · 个数,既与 互素,这样就能证明共有

互素,也与 互素,即定理为真。
版权所有@中国教育考试资源网

上教考资源网
事实上,从第 列看,∵ (若不然,设 , 其中 因题设 数中与 互素的自然数个数正是 这就证明了 ,于是有 ) ,即第 列中存在 。 个与 互素的数。 , 除同余,则 ∴这列中的 个数中,任意两个数被 除时,所得余数都不会相同。

助您教考无忧

可见这第 列中的 个数被 除的余数分别是 0,1,2,3,…, ( -1) (不计顺序) ,而这 个

例 3 求与 300 互素且不超过 300 的自然数的个数。 解 所求的数即

★★★例 4. 试判断是否存在自然数 解 设 则

,使 )

即 这里应估计到 中必有一个是奇数(否则若它们全是偶数,则 ,于是

但 , 只 有

必 是 2 的 倍 数 , 但 它 不 等 于 14 , (否则 , (★★★) 也是素数,因而不可能成立! ) ,于是只能是 且

,不妨令 而 7 是素数,★★★式中

因此也不是成立的! 综上知,不存在 例 5. 试证:
版权所有@中国教育考试资源网



上教考资源网

助您教考无忧

证明: (i)当 是奇数时, (ii)当 是偶数时,不妨设 ,注意到 ,于是

综 i,ii,原命题成立。 例 6. 证明 的值或者是 1 或者是偶数,其中 则 是偶数; 若 ,于是 。 证明: (i)当 =1,2 时, ( )=1; (ii)当 >2 时,若

【能力训练】

1.证明自然数 的所有正约数的欧拉函数值的和为 (即 d 2.设 (m, n) ? d , 则? (mn) ? ? (m)? (n) ? .。 ? (d ) 3.记不大于自然数 而与 互素的数(共 ,求证




版权所有@中国教育考试资源网

上教考资源网

助您教考无忧

参考答案 【能力训练】 1.首先注意,若自然数 这是因为不大于 而与 有公约数 的数只能是 。 现记 ,于是有 不大于 而与 以 不大于 而与 以 ?? 不大于 而与 以 为最大公约数的数有 个; 最大公约数只能是 之一,于是 为最大公约数的数有 为最大公约数的数有 个; 个; ,并注意到: ,即 。

而任何一个不大于 的数与

,即 2.注意

.

3.由 若

可见,1 与 15-1;2 与 15-2;4 与 15-4;都是小于 15 且互素的数,一般而言, 则有 矛盾) 。 (若不然,设 则 ,于是



为不大于 且与 互素的所有自然数,则

也是不大于 且与 互素的所有自然数,从而

版权所有@中国教育考试资源网


数学竞赛书籍推荐

数学竞赛的人不可能没听说这一套书, 这一系列共...高一的这一本包括的知识点有:集合、函数、数列、...(在这个阶段,不等式也不是你的准备重点) 数论方面...

数学奥赛辅导 第三讲 同余

数学奥赛辅导 第三讲 同余知识,方法,技能同余是数论...《中学数学信息网》系列资料 信息网》 WWW.ZXSX....! 定理八: (欧拉函数值计算公式)令 m 的标准分解...

高中数学奥林匹克竞赛介绍

高中数学奥林匹克竞赛介绍_学科竞赛_高中教育_教育...允许使用 任何参考书, 试题以奥妙而奇特的形式见长...数论、几何、组合数学、组合几 何等分类,确定试题...

高中数学知识点总结(最全版)

选修 4—6:初等数论初步。 选修 4—7:优选法与...高中数学 必修 1 知识点 第一章 集合与函数概念 ...可 能同学会看到各种参考上的书写格式不一样, ...

奥数书籍推荐

奥赛经典:超级训练系列高中数学 沈文选主编 湖南...函数》奥林匹克小丛书第二版 11、《奥林匹克数学中...数论给的太少 了。我来说说吧。 第一阶段《...

数学课外书

数论与密码》冯克勤著 3.《迭代 浑沌 分形》李 ...《反证法》孙玉清 015——《高中学生课外阅读系列》...《北京市中学生数学竞赛辅导报告汇集》,北京出版社 1...

数学书籍

数论与密码》冯克勤著 3.《迭代浑沌分形》李忠著...《反证法》孙玉清 015——《高中学生课外阅读系列》...《北京市中学生数学竞赛辅导报告汇集》,北京出版社 1...

论高中数学新课标

是许多高科技(如四大技术——材料、生命、环境、信息...又如在 CT 扫描技术、 计算软件、数论在信息技术中...函数概念三要素确实是高中数学课程中对函数概念学习的...

千余篇数学经典书籍清单汇总欣赏

数论与密码》冯克勤著 3.《迭代 浑沌 分形》李 ...《高中学生课外阅读系列》 ,上海教育出版社 1.《从...《北京市中学生数学竞赛辅导报告汇集》 ,北京出版社 ...

关于重点中学开展数学竞赛工作的实践与认识

基于此,笔者结合 自己从事数学竞赛辅导工作和学校学科...数论、组合数学等高中数学教学内容以外的知识;对竞赛...资料、讲义、信息等资源共享可以让教师有更多的 时间...