当前位置:首页 >> 学科竞赛 >>

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


数论函数
【内容综述】 本讲介绍数论中常见的一些函数的概念、性质及其应用,主要有 除数函数 ——自然数 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

2 m+2

?? ??

r m+r

?? ??

m 2m

2m+1

2m+2

?? ??

2m+r

??

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. 试判断是否存在自然数 解 设 则

,使 )

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

但 则 , 只 有 ,不妨令 而 7 是素数,★★★式中 是

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

因此也不是成立的! 综上知,不存在 例 5. 试证: 。

证明: (i) 当 是奇数时, , 注意到 , 于是

(ii)当 是偶数时,不妨设

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

【能力训练】 1.证明自然数 的所有正约数的欧拉函数值的和为 (即 ) 2.设 (m, n) ? d , 则? (mn) ? ? (m)? (n) ?
d

? (d )

.。

3.记不大于自然数 而与 互素的数(共 ,求证



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

而任何一个不大于 的数与

最大公约数只能是

之一,

于是 2.注意

,即

.

3.由 一般而言,若

可见,1 与 15-1;2 与 15-2;4 与 15-4;都是小于 15 且互素的数, 则有 ,于是 (若不然,设 矛盾) 。 为不大于 且与 互素的所有自然数,则 则



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


相关文章:
数学奥赛辅导 第四讲 不定方程
高中数学奥赛系列辅导资料... 暂无评价 6页 免费喜欢此文档的还喜欢 高中数学奥赛...(如整数、 正整数或有理数)的方程.不定方程是数论的一个重要课题,也是一个...
13【数学】高中数学奥赛的技巧(上篇)
11【数学】高中数学奥赛的... 暂无评价 12页 免费 高中数学奥赛系列辅导资料....11【数学】高中数学奥赛的... 暂无评价 12页 免费 对勾函数研究学习论文 13页...
奥赛辅导材料
高中数学奥赛系列辅导材料 86页 免费 初中化学奥赛辅导材料6 7页 2财富值 初中化学奥赛辅导材料8 8页 2财富值 初中化学奥赛辅导材料7 7页 2财富值 免费!!!201...
高中数学复习辅导材料
1)函数的概念 ) 函数 f 表示每个输入值对应唯一输出值 y 的一种对应关系,记...高中数学奥赛系列辅导材... 86页 免费 重视高中数学中“阅读材... 5页 免费...
2013高中数学奥数培训资料之高斯函数
1/4 同系列文档 2013高中数学奥数培训资料... ...2012年最新高中奥数辅导资料专题,数学联赛获奖不是梦...奥数辅导资料 (内部资料)§28 高斯函数数论函数 y ...
高中数学竞赛资料收集
高中数学竞赛资料收集_学科竞赛_高中教育_教育专区。...数学奥林匹克辅导丛书; 《数学奥林匹克小丛 书 ...高斯函数 重要的数论函数,在数论中用处很多,数量掌握...
11【数学】高中数学奥赛的技巧(中)
3页 10财富值 高中数学奥赛系列辅导资料... 3页 免费喜欢此文档的还喜欢 高中...1 求证 f ( x) 是周期函数。 分析 作特殊化探索。求解的困难在于不知道周期...
数学奥赛辅导 第六讲 集合与映射
高中数学奥赛系列辅导资料... 暂无评价 6页 免费 高中数学奥赛系列辅导资料......而 x 称为 y 的原象,特别当 X 和 Y 都是数集时, 映射 f 称为函数. ...
高中数学奥赛辅导系列-函数的基本性质(一)
高中数学奥赛辅导系列-函数的基本性质(一)。高中数学奥赛辅导系列-函数的基本性质(一)http://www.mathschina.com 彰显数学魅力!演绎网站传奇! 彰显数学魅力!演绎网站...
数学竞赛书
大学出版社* 3、 《奥赛经典:超级训练系列高中...函数》奥林匹克小丛书第二版 11、 《奥林匹克数学...奥赛经典:奥林匹克数学中的数论问题》沈文选 《奥赛...
更多相关标签:
高中生物奥赛辅导教材 | 学而思高中奥赛辅导 | 初高中奥赛辅导好书 | 高中物理奥赛辅导 | 高中化学奥赛辅导书 | 高中化学奥赛辅导 | 高中数学奥赛辅导书 | 高中生物奥赛辅导资料 |