nbhkdz.com冰点文库

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

时间:2014-03-04


上教考资源网
高中数学奥赛系列辅导材料 数论函数
【内容综述】 本讲介绍数论中常见的一些函数的概念、性质及其应用,主要有 除数函数 ——自然数 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 的标准分解...

高中数学竞赛系列讲座01

高中数学竞赛辅导讲座高中数学竞赛系列讲座第一讲 ...高中教材《数学》第一册(上)P23-P23 阅读材料“...由初等数论中定理:a 是大于 1 的整数。如果所有不...

高中奥数经验

《数学选修3-X(忘了哪本) :初等数论初步》 第一...《高中数学联赛考前辅导》熊斌 冯志刚华东师范大学出版...《函数函数方程》奥林匹克小丛书第二版 10、 《...

数学竞赛书籍推荐

他们可以为学生搜集资料,编制试题 细数那些年曾看过...高一的这一本包括的知识点有:集合、函数、数列、...说起余老师, 他绝对算得上是数学竞赛数论这一块...

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

高中数学奥林匹克竞赛介绍_学科竞赛_高中教育_教育...数论、几何、组合数学、组合几 何等分类,确定试题...收集与整理国内 外数学竞赛资料,研究与提炼数学竞赛...

高中数奥经验

高中数学联赛考前辅导》熊斌 冯志刚华东师范大学出版...《函数函数方程》奥林匹克小丛书第二版 10、 《...奥林匹克小丛书《柯西不等式与平均值不等式》 数论(...

数学电子书

《中等数学》连载《高中奥数训练题》59套.pdf 1-....pdf 代数数论导引_张贤科.pdf 代数体函数与常微分...(何书元).pdf 中学数学奥林匹克竞赛辅导.pdf 状态...