数论函数 （教案）高中数学奥赛教程集.docVIP

学科：奥数 教学内容：数论函数 【内容综述】 　　除数函数——自然数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.欧拉函数 互素且不大于的自然数的个数(),称为欧拉函数。 ，易证是素数（∵每个小于的自然数都与它互素）；反之可见，若是合数，必有。 　　关于欧拉函数，有以下性质定理 　　定理４ 设P是素数，且 　　证明 ∵P是素数，显然有互素的充要条件是，即有：，反之若，且知在1和个数是p的倍数： ，而其余的数都与互素，从而可知不超过且与互素的自然数个数。 　　当自然数的素因数分解式中，不只包含一个素因数时，有 　　定理5 设大于1的自然数的素因数分解式为 ， 　　其中则有 　　　　 　　证明：因为素因数的个数，故考虑采用数学归纳法（下设表有k个素因数的自然数 　　（i）当 　　（ii）设 　　注意到加入第个k+1素因数 　　　　， 　　且当 　　于是由归纳假设就有 　　 　　从而时，定理成立； 　　综上，对任意 （★的补证： 引理 设、c∈N，则(i)若 　　　　, 　　　　从而 　　　　可见 　　　　故 　　　　同理可证 （ii）若，由 　　　　 　　　　同理，若 　　　　再证定理 若 　　　　 （★★） 　　注意到，故中有一个数为1时，（并把从1到方阵： 1 2 …… r …… m m+1 m+2 …… m+r …… 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. 试判断是否存在自然数，使 解 设 　　则 　　　 　　即 　　这里应估计到中必有一个是奇数（否则若它们全是偶数，则，于是 　　　　 　　但必是2的倍数，但它不等于14，（否则，且，不妨令 （★★★） 　　而7是素数，也是素数，因而不可能成立！），于是只能是 　　　　 　　　　 　　　　 　　因此也不是成立的！ 　　综上知，不存在。 　　例5. 试证： 证明： 　　（i）当，注意到，于是 　　（ii）当 　　　　　 　　综i,ii，原命题成立。 6. 证明1或者是偶数，其中 　　证明： （i）当=1，2时，）=1； （ii）当2时，若 　　　　是偶数； 　　若，于是 　　　　 　　 【能力训练】 　　1．证明自然数（即） 　　2．设 　　3．记不大于自然数互素的数（共，求证。 　　参考答案 　　【能力训练】 　　1．首