（基础数学专业论文）关于一个数论函数的问题.pdf

苏州大学学位论文使用授权声明 i i i ii iii i i i iiiii ll liil y 17 3 2 3 3 8 本人完全了解苏州大学关于收集、保存和使用学位论文的规定， 即：学位论文著作权归属苏州大学。本学位论文电子文档的内容和纸 质论文的内容相一致。苏州大学有权向国家图书馆、中国社科院文献 信息情报中心、中国科学技术信息研究所( 含万方数据电子出版社) 、 中国学术期刊( 光盘版) 电子杂志社送交本学位论文的复印件和电子 文档，允许论文被查阅和借阅，可以采用影印、缩印或其他复制手段 保存和汇编学位论文，可以将学位论文的全部或部分内容编入有关数 据库进行检索。 涉密论文口 本学位论文属在年月解密后适用本规定。 非涉密论文口 ， 论文作者签名： 拳选墼日期：也绎扫i 里 导师签名：三二 兰皇 日 期：! 旦墨! 盈主2 关于个数论函数的问题 摘要 关于一个数论函数的问题 摘要 本文在第一章中首先介绍最大公约数，整数的标准分解，同余，孙子定理，积 性函数等一些基本概念及结果。第二章给出a ( 1 ，n ) 的一个表达式，并指出a ( 1 ，n ) 关 于七的单调性第三章对 ( o ，n ) 与f k ( 1 ，n ) 进行比较，得出它们之间的大小关系第 四章则进一步分析厶( o ，亿) 关键词：最大公约数；数论函数； 同余 作者：朱建霞 指导老师：余红兵教授 a b s t r a c to ns o m ep r o b l e m so fa l la r i t h m e t i c a lf u n c t i o n o ns o m ep r o b l e m so fa na r i t h m e t i c a lf u n c t i o n a b s t r a c t i nt h ef i r s tc h a p t e ro ft 地p a p e r w ei n t r o d u c et h ed e f i n i t i o no ft h eg r e a t e s tc o m m o n d i v i s o r ，c o n g r u e n c e ，c h i n e s er e m a i n d e rt h e o r e m ，m u l t i p l i c a t i v ef u n c t i o n ，a n ds oo n i nt h e s e c o n dc h a p t e r ，w eg i v eaf o r m u l ao f ( 1 ，礼) a n dd i s c u s st h em o n o t o n i c i t yo f ( 1 ，n ) o n 七 t h et h i r dc h a p t e r ，w ec o m p a r e ( o ，礼) a n d ( 1 ，扎) ，a n do b t a i nas i z er e l a t i o n s h i pb e t w e e n t h e m i nt h ef o u r t hc h a p t e r ，w ew i l lf u r t h e ra n a l y s i saa ，n ) k e y w o r d s ：t h eg r e a t e s tc o m m o nd i v i s o r ；a r i t h m e t i c a lf u n c t i o n ；c o n g r u e n c e i i w r i t t e nb yz h uj i a nx i a s u p e r v i s e db yp r o f y uh o n g b i n g 关于一个数论函数的问题 目录 目录 第一章基本知识3 第二章关于f k ( 1 ，凡) 的一个结果6 2 1 一些记号6 2 2 问题的提出6 2 3 预备引理7 2 4 定理2 1 及定理2 2 的证明7 第三章 ( n ，n ) 与 ( 1 ，n ) 的关系1 2 3 1 一些记号1 2 3 2 问题的提出1 2 3 3 定理的证明1 2 第四章 ( n ，礼) 的进一步讨论1 6 4 1 问题的提出1 7 4 2 预备引理1 7 4 3 定理的证明1 8 参考文献2 2 致谢2 3 关于一个数论函数的问题引言 引言 数论函数是指定义在整数集( 或者其某个子集) 上，而值为复数的函数数论中自 然地产生许多这样的函数，如欧拉函数咖( 礼) 、m s b i u s 函数p ( n ) 等( 可以参考c 1 】) 数 论函数在数论及组合数学等领域都占有十分重要的位置，因而对其值的研究也有了特 殊的意义 设k ，n 为正整数， a 为整数，记满足a d ，d + 1 ，d + k 一1 a + n 一1 ，且 ( d ，n ) = ( d + 1 ，n ) = = ( d + k 一1 ，几) = 1 的d 的个数为a ( n ，n ) 我们首先给出了 ( 1 ，礼) 的一个表达式，并指出 ( 1 ，n ) 关于k 的单调性；其次比较 ( o ，n ) 与 ( 1 ，礼) ， 得出它们之间的大小关系；最后，借助得到的结论再对 ( 口，n ) 作进一步分析 腓臀卜和：盱欷孙； 定理2 2 ( 1 ) f k ( 1 ，几) 关于k 是递减函数 ( 2 ) a ( 1 ，n ) 一a + 1 ( 1 ，礼) a + 1 ( 1 ，n ) 一 + 2 ( 1 ，n ) ，其中等号成立当且仅当 佗= p a 或 ( 1 ，礼) = a + 1 ( 1 ，n ) = + 2 ( 1 ，n ) = 0 定理3 1 f ，2 ( n ，礼) = 【 尼( 1 ，n ) 一1 ，( a ，n ) = ( a 一1 ，佗) = 1 ； f 2 ( 1 ，佗) ， 否则 定理3 2 ( 1 ，几) 一k + 15 ( 口，n ) ( 1 ，礼) 1 引言关于数论函数的一个问题 定理4 1 设扎，k 是给定正整数，对于i = 1 ，k ，若记满足 ( ，扎) = 厶( 1 ，n ) 一k + i 的正整数a ( 1 a n ) 的个数为帆n ( i ) ，则有t ( 1 ) 帆，n ( 1 ) + 帆，n ( 2 ) + + 帆，n ( 后) = 佗， ( 2 ) n k ，n ( 1 ) = ，2 南一2 ( 1 ，n ) ， ( 3 ) k ，n ( i ) = i ( 2 k 一 一1 ( 1 ，礼) + 丘七一i + 1 ( 1 ，n ) 一2 f 2 k i ( 1 ，n ) ) + 2 ( 厂2 _ | c i ( 1 ，礼) 一，2 七一i + 1 ( 1 ，n ) ) ， 其中2 i k 一1 七一1 注：( 1 ) 由定理4 1 知，帆n ( ) = n 一胍，n ( 1 ) i = 1 ( 2 ) 由定理2 1 可知，对于给定的正整数七，n ，可实效的确定n k ，。( t ) ( 对每一个) 定理4 2 给定正整数忌，n ，对i = 1 ，k ，数n ( i ) 0 的充分必要条件是n 的最小 素因子 2 k 一2 本文的主要内容安排如下： 第一部分引言 第二部分给出本文涉及到的基本知识和基本定理 第三部分给出定理2 1 及定理2 2 证明 第四部分给出定理3 1 及定理3 2 证明 第五部分给出定理4 1 及定理4 2 证明 2 关于一类数论函数的问题 第一章基本知识 第一章基本知识 本文涉及到数论中的一些基本概念与结果，本章就此作一些简单介绍( 参见 1 】) 1 1 整除 定义1 1设a 和b 是整数，b 0 如果存在整数c 使得a = 6 c ，则我们称b 整除 a ，记作ba ，并称b 是a 的一个约数，a 是b 的倍数如果不存在这样的c ，则称b 不整除a ，记作b f a 设整数p 0 ，1 如果它除了约数士1 ，士p 外没有其他的约数，那么p 就称为素 数 自然数唯一分解及标准分解： ( 1 ) 每个不大于1 的正整数均可分解为有限个素数的乘积； ( 2 ) 如果不计素因子在乘积中的次序，则( 1 ) 中的分解方式是唯一的 对每一个大于1 的正整数n ，将其分解中相同的素因子收集在一起，即知几可唯一 的表示为佗= p 1 p 呈2 p 芋。，其中，p l ，p 2 ，p ，为互不相同的素数，q l ，q 2 ，q 。 为正整数，这称为n 的标准分解 1 2 最大公约数 定义1 2设a ，b 是不全为零的整数，满足下面两个条件的唯一的d 称为它们的最 大公约数，记作( a ，6 ) ( 1 ) d 是a ，b 公约数，即da ，d1 6 ； ( 2 ) d 是a ，b 的所有公约数中最大的，即如果整数d 1 也是a ，b 的公约数，则d l d 如果( a ，b ) = 1 ，则称a ，b 是互素的 1 3 同余 定义1 3设m 0 ，若mla b ，即a b = k m ，则称m 为模，a 同余于b 模m ，记 作a 三b ( 仇d dm ) 3 第一章基本知识关于数论函数的一个问题 定义1 4 对给定的模m ，全体整数按对模m 是否同余分为若干个两两不相交的集 合，使得同一集合中的任意两个数对模m 同余，而属于不同集合中的任意两个数对模 不同余，每一个这样的集合称为模m 的同余类或模m 的剩余类 定义1 5 m 个整数c 1 ，c m 称为模m 的完全剩余系，是指彼此模m 不同余 1 4 孙子定理 定理1 1 设m l ，m k 是两两互素的正整数，那么，对任意整数a 1 ，a 七，一次同 余方程组x 三a i ( m o dm d ，l i k 必有解，且解数为1 ，且它的解是z 兰尬m r l a l + + m k m 1 a k ( m o dm ) 这里m = m l m k ，m = m t 舰( 1 i 七) ，以及舰是满足 尬岈1 兰1 ( m o dm t ) ，1 i k 的一个整数 证明：见 1 , p 1 7 0 注：孙子定理实质上刻画了剩余系的结构 定理1 2 设m l ，m k ，m ，尬，m k ，圻1 ，m k l 同定理1 1 ， 再设z = 尬圻1 z ( 1 ) + + m k m k l z ( 那么， z 过模m 的完全剩余系的充要条件是分别过模m i 的完全剩余系，其中1 i k 证明：设y = m 1 m - 1 耖( 1 ) + + m k m 1 可( 扪，则 z 三y ( r o o dm ) ，即尬a 叮1 ( z ( 1 ) 一剪( 1 ) ) + + m ka 钌1 ( z ( 七) 一暑( ) ) 三0 ( r o o dm ) 由m ，尬，地，及圻1 ，岈1 的定义知， z ( ) 一( ) 三0 ( r o o dm ) l i k 即z ( ) 三y ( ) ( r o o dm t ) l i k 所以， z 三y ( m o d 仇t ) ，从而z 兰y ( m o dm ) 我们有x 三y ( m o dm ) 的充分必要条件是z ( ) 三! ，( ) ( m o dm ) 1 i k 因此，由孙子定理可知，定理1 2 得证 1 5 数论函数 定义1 6我们把定义在整数集合z 上的复值函数y = ，( n ) 称为数论函数一个数 论函数f ( n ) 是积性的，如果它对于任意的m ，n z ，( m ，n ) = 1 ，有 f ( m n ) = ，( m ) ，( n ) 4 关于一类数论函数的问题第一章基本知识 我们注意，若f ( n ) 是积性函数，设佗有标准分解n = p l a 船a 。p s “，则我们有 8 伽) = f ( p i 啦) i = 1 基本的数论函数 定义1 7设n 是正整数，1 ，2 ，佗中与, - 1 互素的数的个数称为e u l e r 函数，记作 ) 5 第二章关于 ( 1 ，n ) 的一个结果 关于一个数论函数的问题 2 1 一些记号 第二章关于 ( 1 ，n ) 的一个结果 本章将涉及到一些数论函数的问题，我们首先对这些概念及记号作一些说明 定义2 1 设k ，n 为正整数，记满足l d ，d + l ，d + k 一1 佗，且( d ，佗) = ( d + l ，礼) = = ( d + k l ，佗) = l 的d 的个数为f k ( 1 ，仃) 定义2 2 设k ，佗为正整数，记满足1 d n ，且( d ，佗) = ( d + 1 ，n ) = = ( d + k 一 1 ，n ) = l 的d 的个数为丘( 1 ，n ) 2 2 问题的提出 由上述定义可知，f k ( 1 ，n ) = 厶( 1 ，n ) ，所以，为了得到f k ( 1 ，n ) 的结果，我们研究 五( 1 ，礼) 众所周知，咖( 竹) = 礼l - i ( 1 一：) ，又由五( 1 ，礼) 的定义，我们可以看出， 当k = 1 时，石( 1 ，n ) = ( n ) ，即片( 1 ，n ) = nl - i ( 1 一：) ；对于k = 2 ，可以证明 f 2 ( 1 ，n ) = n 1 - - ( 1 一：) 见 1 ，p a 0 6 上述结果给出了k = 1 ，2 时，丘( 1 ，扎) 的值本章我 们主要的工作是借助f k ( 1 ，n ) 证明下述的定理2 1 ，定理2 2 定理2 1 设厶( 1 ，佗) 由( 2 1 ) 定义，则有 f 川哩( 1 一；) ，n 的素因子都大于七， ( 1 ，礼) ： 叫” 【0 ， 否则 注此结果是本文的一个基础，在后面工作中将多次使用 定理2 2 ( i ) y k ( 1 ，n ) 关于k 是递减函数 ( 2 ) f k ( 1 ，竹) 一九+ 1 ( 1 ，n ) + 1 ( 1 ，几) 一a + 2 ( 1 ，礼) ，其中等号成立当且仅当 仃= p a 或f k ( 1 ，n ) = 九+ 1 ( 1 ，n ) = + 2 ( 1 ，n ) = 0 6 关于一个数论函数的问题第二章关于丘( 1 ，n ) 的一个结果 2 3 预备引理 引理2 1 ( 容斥原理 2 p 1 2 1 ) 设a 1 ，a 2 ，厶是有限集合，则 一+ ( 一1 ) ”一1 i a ln a 2n na n i ( 木) 这是一个熟知的结果，为了完备起见，我们给出其证明 证明对任意a ，若属于a 1 ，a 2 ，中任意k 个( 1 k n ) 则 a 在( 木) 式左边贡献1 ，a 在( 木) 式右边贡献为 ( ：) 一( ：) + ( ；) + + c 一1 ，一1 ( 羔) = 若a 不属于a 1 ，a 2 ，九中任意一个，则 a 在( 宰) 式两边均贡献0 故( 木) 式得证 2 4 定理2 1 及定理2 2 的证明 定理2 1 的证明 首先，证明丘( 1 ，礼) 是关于n 的积性函数 j 没n = n ln 2 ，( n l ，n 2 ) = 1 ，n 1n f l 兰1 ( r o o d 死2 ) ，n 2 礼i 1 兰l ( m o dn 1 ) ， 则由定理1 2 ，得 d = n 2 佗i l d l + n ln 1 1 d 2 ，( 2 1 ) 过模n 的一个完全剩余系的充分必要条件是 d 1 过模扎。的完全剩余系，d 2 过模n 2 的完全剩余系 ( d ，n ) = 1 兮( d ，n l n 2 ) = 1 兮( d ，n 1 ) = 1 ，( d ，n 2 ) = 1 铮( d l ，? 2 1 ) = 1 ，( d 2 ，佗2 ) = 1 ( d + 1 ，n ) = 1 兮( d + 1 ，n l n 2 ) = 1 铮( d + 1 ，n 1 ) = 1 ，( d + 1 ，n 2 ) = 1 营( d a + 1 ，? 2 1 ) = 1 ，( d 2 + 1 ，n 2 ) = 1 ( d + k 一1 ，n ) = 1 营( d + k 一1 ，_ ，2 1 n 2 ) = 1 兮( d + k 一1 ，r $ 1 ) = 1 ，( d + k 一1 ，n 2 ) = 1 铮 7 乱 n 如n 如 跏 n 澍 + 冬n 钆 。汹 一 生 仃沮 = n a uu 赴 u 钆 第二章关于 ( 1 ，礼) 的一个结果 关于一个数论函数的问题 所以，五( 1 ，佗) = 以( 1 ，佗1 ) f k ( 1 ，佗2 ) ，即以( 1 ，n ) 是积性函数 f k ( 1 ，n ) = h f k ( 1 ，p i 口) = 五( 1 ，矿) ， 所以，我们只要计算无( 1 ，矿) 若p k ，则冗( 1 ，矿) = 0 ，所以，若佗存在小于等于k 的素因子， 则有，丘( 1 ，n ) = nf k ( 1 ，p a ) = 0 若p 七，则0 ，1 ，2 ，七一1 为模p 的后个同余类 f k ( 1 ，矿) = p 口一， 和臀1 争：酹默； 8 关于一个数论函数的问题 第二章 关于 ( 1 ，n ) 的一个结果 c ，n ，= ：? 。一知三：_ 因子都大于如 脚，= 甚 所以，我们要证 ( 1 ，n ) = ( 1 ，n ) 一a + 1 ( 1 ，n ) = f k + l ( 1 ，n ) 一a + 2 ( 1 ，n ) 只要证 p a ( 1 - ；k ) 卅1 一字) = p a ( 1 一字) 训l 一字) 等式两边同除p 铲1 ，上式即为 p k ) 一( p 一( 庇+ 1 ) ) = ( p 一( 七十1 ) ) 一p 一( k + 2 ) ) ， 此式显然成立 所以当n = p a 时，f k ( 1 ，n ) 一 + 1 ( 1 ，n ) = + 1 ( 1 ，n ) 一 + 2 ( 1 ，n ) 9 七一p 卜 一 七一p 0 一 t l n l t上列弋叫；矿 第二章 关于 ( 1 ，n ) 的一个结果 关于一个数论函数的问题 下设佗的标准分解为他= p l a ，p 2 口2 乳m ，其中8 1 若f k ( 1 ，n ) = 厶+ 1 ( 1 ，佗) = f k + 2 ( 1 ，n ) = 0 贝4 易得 厶( 1 ，n ) 一 + 1 ( 1 ，礼) = + 1 ( 1 ，礼) 一a + 2 ( 1 ，佗) 若y k ( 1 ，n ) o ， + 1 ( 1 ，n ) = f k + 2 ( 1 ，n ) = 0 ，贝4 a ( 1 ，n ) 一f k + 1 ( 1 ，他) f k + l ( 1 ，礼) 一f k + 2 ( i ，n ) 若丘+ 1 ( 1 ，n ) 0 ， + 2 ( 1 ，礼) = 0 ，则n 的素因子均大于等于k + 2 ，且存在素因子等于 k + 2 不妨设p 1 = k + 2 ， 此时要证 ( 1 ，n ) 一f k + l ( 1 ，佗) f k + 1 ( 1 ，礼) 一a + 2 ( 1 ，n ) ， 只要证 ( 1 ，n ) 2 f k + 1 ( 1 ，佗) ，即 n i i ( ，一石k ) 2 n i i ( - 一字) ， p l np l n 不等式两边同除p l a 一1 p 2 q z 仇a ，上式即为 p l 一七) 一k ) 。一k ) 2 ( p i 一( k + 1 ) ) 纰一( k + 1 ) ) 一( k - i - 1 ) ) 将p 1 = k + 2 代入上式，即为 2 慨一k ) 慨一k ) 2 ( p 2 一( k - i - 1 ) ) 慨一( k + 1 ) ) 此式显然成立 所以，当 + i ( 1 ，n ) 0 ，f k + 2 ( i ，礼) = 0 时，f k ( 1 ，n ) 一 + 1 ( 1 ，几) + 1 ( 1 ，n ) 一f k + 2 ( 1 ，n ) 若厶+ 2 ( 1 ，n ) 0 ，此时要证 ( 1 ，佗) 一 + l ( 1 ，n ) + 1 ( 1 ，礼) 一f k + 2 ( 1 ，他) ， 即 n 婴( 一石k ) + 礼娶( 1 一字) 2 n 娶( 一字) p i n p i n 1 p i n 1 1 0 关于一个数论函数的问题 第二章 关于 ( 1 ，几) 的一个结果 不等式两边同除p l a - - 1 p 2 a 。p 。a 。，上式即为 ( p l k ) ( p 2 一k ) 仞。一七) + 1 一( k - 4 - 2 ) ) 慨一( k - 4 - 2 ) ) 0 。一( 南+ 2 ) ) 2 ( p l 一( k + 1 ) ) 2 一( k + 1 ) ) 饥一( 老+ 1 ) ) 记q i = p i 一( k + 1 ) ，其中1 i 8 ， 由a + 2 ( 1 ，n ) 0 知， 礼的素因子均大于k + 2 ，即p i k + 2 ，( 1 i s ) 所以， q i 1 ，其中1 i s 将吼= p t 一( k + 1 ) ，( 1 i 8 ) 代入上式，即为 ( q 1 + 1 ) ( q 2 + 1 ) ( q 。+ 1 ) + ( 口1 一1 ) ( q 2 1 ) ( q 。一1 ) 2 q l q 2 口s 将上述式子左边展开可见( q l 一1 ) ( q 2 1 ) ( q s 一1 ) 中的负项将与( q l + 1 ) ( q 2 + 1 ) ( q s + 1 ) 中对应正项相消，又因为对所有l i 8 ，有q i l ，所以，上式成立 所以，当a + 2 ( i ，礼) 0 时， 综上所述 a ( 1 ，n ) 一 + 1 ( 1 ，几) f k + l ( 1 ，n ) 一a + 2 ( 1 ，n ) ( 1 ，n ) 一 + 1 ( 1 ，几) a + i ( 1 ，礼) 一a + 2 ( i ，n ) ， 其中等号成立当且仅当 n = p a 或 ( 1 ，他) = 厶+ 1 ( 1 ，佗) = a + 2 ( i ，n ) = 0 第三章 ( n ，n ) 与九( 1 ，n ) 的关系关于一个数论函数的问题 第三章f k ( a ，n ) 与f k ( 1 ，佗) 的关系 3 1 一些记号 我们首先对本章涉及的记号作一些说明 定义3 1 设k ，礼为正整数，n 为整数，记满足n d ，d + 1 ，d + k 一1 a + n 一1 ， 且( d ，n ) = ( d + 1 ，n ) = = ( d + k 一1 ，礼) = 1 的d 的个数为 ( o ，他) 注：当口= 1 时， ( n ，n ) 即为第二章中的f k ( 1 ，几) 3 2 问题的提出 由定义3 1 我们得到：f l ( 1 ，礼) = ( 礼) 因为o ，a + 1 ，o + n 一1 是模7 , 的一个完全剩余系，所以f 1 ( 2 ，n ) = ( 几) ， 从而，f l ( a ，礼) = f 1 ( 1 ，佗) 我们在上一章中已经给出厶( 1 ，n ) 的一个表达式，那么k ( 2 ，n ) 与k ( 1 ，n ) 的关系又如 何? 为此，我们首先考虑，2 ( n ，佗) 与y 2 ( 1 ，n ) 的关系，得到定理3 1 ；其次分析 ( ，n ) 与 f k ( 1 ，n ) 的关系，具体结果请见下述定理3 2 3 3 定理的证明 定理3 1 设f 2 ( 2 ，n ) 由定义( 3 1 ) 给出，则有 f1 2 ( 1 ，n ) 一1 ，( n ，竹) = ( n l ，7 , ) = 1 ； 尼( n ，n ) = 【1 2 ( 1 ，佗) ， 否则 证明 由定义( 3 1 ) 可得，2 ( o ，佗) 关于a 以n 为周期，所以我们只要对1 a n 证 明即可 1 2 关于一个数论函数的问题第三章 ( n ，凡) 与a ( 1 ，n ) 的关系 对于给定正整数口，n ，f 2 ( a ，n ) 为 a ，a + 1 ，凡，n + 1 ，a + n 一1 ，( 3 1 ) 中满足( d ，礼) = ( d + 1 ，佗) = 1 的d 的个数，其中a d ，d + 1 a + n 一1 z 2 ( 1 ，n ) 为 1 ，2 ，a l ，a ，a + 1 ，几，( 3 2 ) 中满足( d ，n ) = ( d + 1 ，几) = 1 的d 的个数，其中1 d ，d + 1 几 注意到 满足n + l d ，d + l a - t - n 一1 且( d ，凡) = ( d + l ，n ) = 1 的d 的个数与满足1 d ，d - t - 1 a - 1 且( d ，n ) = ( d + 1 ，n ) = l 的d 的个数相同 将( 3 1 ) 中a ，a + l ，礼与( 3 2 ) 中n ，a + 1 ，n 对应， 将( 3 1 ) 中礼+ 1 ，n + 2 ，n + n l 与( 3 2 ) 中1 ，2 ，n 一1 对应 所以，y 2 ( a ，n ) 与f 2 ( 1 ，几) 区别取决于各自的连接处a 一1 ，a 与n ，n + l 是否与n 互素 所以，当( a 一1 ，n ) = ( a tn ) = 1 时，2 ( o ，凡) = f 2 ( 1 ，n ) 一1 ；否则，2 ( o ，n ) = f 2 ( 1 ，n ) 注1 ：在研究，2 ( 口，n ) 与厶( 1 ，n ) 的关系时，我们首先通过数值检验，猜测应该有 ，2 ( ，n ) ，2 ( 1 ，佗) ，( 3 3 ) 并且用数学归纳法给予了证明，进一步，我们发现，应该还有 丘( o ，n ) ，2 ( 1 ，n ) 一1 ， ( 3 4 ) 即f 2 ( a ，n ) = ，2 ( 1 ，n ) 或，2 ( o ，n ) = f 2 ( 1 ，礼) 一1 然而( 3 4 ) 似乎不易用归纳法证明，后 来，我们采用组合角度的处理，发现更强的结论( 即定理3 1 ) ，事实上更容易证明 注2 ：不等式( 3 3 ) 的归纳证明似乎有些独立的趣味，因此我们在此给出其证明 命题，2 ( 口，n ) 厶( 1 ，n ) 证明 由定义( 2 1 ) 可知，2 ( o ，佗) 关于。以n 为周期，所以我们只要对1 n n 证 明即可 对a 归纳： 】3 第三章 ( o ，佗) 与f k ( 1 ，几) 的关系 关于一个数论函数的问题 当口= 1 时，如( o ，n ) = 2 ( 1 ，竹) ；当n = 2 时，f 2 ( a ，n ) = 1 2 ( 1 ，n ) 一1 假设当d 仇时， ，2 ( n ，n ) ，2 ( 1 ，礼) 当口= m + 1 时，若，2 ( m ，仃) y 2 ( 1 ，礼) 这与归纳假设矛盾 所以，( 仇一2 ，n ) = 1 ，且f 2 ( m 一1 ，n ) = f 2 ( m ，佗) = f 2 ( t ，礼) 此时，再对m 一3 讨论， 如果( m 一3 ，n ) 1 ，将有丘( m 一2 ，n ) = ，2 ( m 一1 ，竹) + 1 庀( 1 ，礼) ，矛盾 所以，( m 一3 ，n ) = 1 ，且丘( m 一2 ，佗) = 南( m 一1 ，n ) = f 2 ( m ，几) = ，2 ( 1 ，n ) 依次继续对m 一4 ，m 一5 ，2 讨论，得： ( m 一2 ，7 1 , ) = ( m 一3 ，礼) = = ( 2 ，n ) = 1 ，且丘( 2 ，礼) = 丘( 3 ，礼) = = 丘( m ，n ) = y 2 ( 1 ，n ) 而f 2 ( 2 ，n ) = 丘( 1 ，n ) 一1 ，所以上式不成立 这说明当，2 ( m ，n ) = ，2 ( 1 ，n ) ，且( m ，n ) = l 时，( m 一1 ，凡) = 1 不可能， 综上可得： f 2 ( m + 1 ，r , ) f 2 ( 1 ，n ) 所以，由归纳法有：y 2 ( a ，n ) ，2 ( 1 ，n ) 下面给出血( n ，n ) 与 ( 1 ，仃) 的关系 定理3 2a ( 1 ，n ) 一船+ 1 丘( o ，礼) a ( 1 ，n ) 证明 由于 ( n ，n ) 关于。以n 为周期，所以只要对1 口n 证明即可 对于给定正整数o ，n ，k ( a ，扎) 为 口，n + 1 ，n ，n + 1 ，o + n 一1 ，( 3 5 ) 中满足( d ，死) = ( d + 1 ，n ) = = ( d + 后一1 ，n ) = l 的d 的个数，其中 口d ，d + 1 ，d + 七一1 n + n 一1 1 4 关于一个数论函数的问题 第三章h ( a ，佗) 与f k ( 1 ，凡) 的关系 ( 1 ，r , ) 为 1 ，2 ，a 一1 ，a ，a + 1 ，n ， ( 3 6 ) 中满足( d ，礼) = ( d + l ，7 2 ) = = ( d4 - k 一1 ，n ) = l 的d 的个数，其中 l d ，d4 - 1 ，d4 - k 一1 7 2 。 注意到： 满足n4 - l d ，d + k 一1 a4 - n 一1 且( d ，礼) = ( d 4 - 1 ，n ) = = ( d 4 - k 1 ，n ) = 1 的 d 的个数与满足l d ，d + k 一1 a 一1 且( d n ) = ( d 4 - 1 ，礼) = = ( d 4 - k 一1 ，n ) = 1 的d 的个数相同 将( 3 5 ) 中o ，a4 - 1 ，n 与( 3 6 ) 中a ，a4 - 1 ，n 对应， 将( 3 5 ) 中礼4 - 1 ，n4 - 2 ，a4 - 他一1 与( 3 6 ) 中1 ，2 ，a 一1 对应 所以， a ( o ，几) 与a ( 1 ，佗) 区别取决于各自的连接处产生的数是否与n 互素， a ，扎与n4 - 1 ，a4 - n 一1 连接至多产生如下k l 组连续k 个数， 礼一k + 2 ，n k4 - 3 ，礼，n4 - l ， n k4 - 3 ，n ，礼4 - 1 ，7 , 4 - 2 ， ( 3 7 ) n ，礼4 - 1 ，n 4 - 2 ，佗4 - 七一1 而1 ，a 一1 与a ，n 连接至多产生如下k 1 组连续k 个数， a k4 - 1 ，a k4 - 2 ，a 一1 ，a ， a k4 - 2 ，a 一1 ，a ，a4 - 1 ， ( 3 8 ) a l ，a ，a4 - 1 ，a4 - 七一2 由于( 3 7 ) 的每组连续k 个数均含有n ，即每组都不满足连续k 个数与礼互素， 所以，对比( 3 7 ) ，( 3 8 ) 得到： a ( 1 ，n ) 一k4 - 1 ( 口，n ) ( 1 ，扎) 1 5 第三章 ( n ，n ) 与f k ( 1 ，n ) 的关系 关于一个数论函数的问题 注3 ：由上述证明可见，设正整数七，他给定，对1 i5 七，我们有 正整数a ( 1 a n ) 满足a ( o ，n ) = ( 1 ，礼) 一k + i 兮 ( 3 8 ) 中有且仅有岛一i 组数满足每组的连续k 个数与n 互素 ( 奉) 但这一结果非实效，因为我们不易给出n 的刻划使得( 奉) 式成立 注4 ：若忌大于扎的最小素因子，则由定理2 1 可知， ( 1 ，n ) = 0 ，又总有a ( o ，n ) 0 ， 从而由定理3 2 可知， ( o ，n ) = 0 ，对所有整数a 1 6 关于数论函数的一个问题第四章 厶( n ，佗) 的进一步讨论 第四章f k ( a ，死) 的进一步讨论 4 1 问题的提出 在前一章中，我们证明了，对于给定的正整数，n 及整数a ，有一个i ( 1 i 忌) ，使得 a ( o ，礼) = a ( 1 ，n ) 一k + i 一个自然的问题，对于一个满足1 i k 的i ，是否存在以及有多少个相应的 整数a ( 1 a n ) ，使上式成立 本章，我们将研究这一问题，具体结果请见下述定理4 1 及定理4 2 4 2 预备引理 弓i 理4 11 d 几，则 ( 1 ) 满足( d ，n ) = ( d + 1 ，佗) = = ( d + 一1 ，佗) = 1 ，( d + k ，礼) 1 的d 的个数为 ( 1 ，仃) 一f k + l ( 1 ，n ) ( 2 ) 满足( d ，佗) = ( d + 1 ，n ) = = ( d + k 一1 ，佗) = 1 ，( d 一1 ，n ) 1 的d 的个数为 ( 1 ，n ) 一f k + l ( 1 ，n ) ( 3 ) 满足( d ，n ) = ( d + 1 ，n ) = = ( d + k l ，礼) = 1 ， 一1 ，几) 1 ，且( d + k ，n ) 1 的d 的个数为f k ( 1 ，礼) 一2 + 1 ( 1 ，n ) + a + 2 ( 1 ，礼) 证明( 1 ) 分析d + k ，将( d ，n ) = ( d + 1 ，佗) = = ( d + k 一1 ，7 , ) = 1 分为两种情况 ( d ，n ) = ( d + l ，佗) = = ( d + k 一1 ，佗) = l ( d + k ，n ) = l ，( 4 1 ) ( d ，凡) = ( d + 1 ，礼) = = ( d + k 一1 ，n ) = 1 ，( d + ，n ) 1 ( 4 2 ) 根据定义2 1 ，满足( 4 1 ) 的d 的个数为 + 1 ( 1 ，他) ，而满足( 反n ) = ( d + 1 ，n ) = = ( d + k 一1 ，n ) = 1 的d 的个数为f k ( 1 ，几) 所以，满足( 4 2 ) 的d 的个数为a ( 1 ，n ) 一九+ 1 ( 1 ，n ) ， 即( 1 ) 成立 ( 2 ) 分析d 一1 ，将( d ，n ) = ( d + 1 ，礼) = = ( d + 惫一1 ，n ) = 1 分为下述两种情况 ( d 一1 ，礼) = l ，( d ，礼) = ( d + 1 ，礼) = = ( d + 七一1 ，n ) = 1 ，( 4 3 ) 1 7 第四章 ( 口，几) 的进一步讨论关于数论函数的一个问题 ( d 一1 ，n ) 1 ，( d ，礼) = ( d + 1 ，礼) = = ( d + k 一1 ，n ) = 1 ( 4 4 ) 根据定义2 1 ，满足( 4 3 ) 的d 一1 的个数为a + 1 ( 1 ，n ) ；相应的，满足( 4 3 ) 的d 的个数 也为 + 1 ( 1 ，n ) 而满足( d ，礼) = ( d + 1 ，r , ) = = ( d + k 一1 ，竹) = 1 的d 的个数为f k ( 1 ，n ) 所以，满足( 4 4 ) 的d 的个数为f k ( 1 ，n ) 一 + l ( 1 ，n ) ，即( 2 ) 成立 ( 3 ) 对d 一1 ，d + k 分析，将( 以n ) = ( d + l ，n ) = = ( d + k 一1 ，礼) = 1 分为下述四种情况 ( d l ，n ) = l ，( d ，礼) = ( d + 1 ，礼) = = ( d + k 一1 ，几) = 1 ，( d + 七，n ) = 1 ， ( d 一1 ，佗) = 1 ，( d ，n ) = ( d + l ，n ) = = ( d + k 一1 ，佗) = 1 ，( d + k ，n ) l ， ( d 一1 ，亿) l ，( d ，n ) = ( d + 1 ，礼) = = ( d + k 一1 ，佗) = 1 ，( d + k ，n ) = 1 ， ( d l ，n ) 1 ，( d ，礼) = ( d + 1 ，n ) = = ( d + k 一1 ，n ) = 1 ，( d + k ，t i , ) 1 ( 4 5 ) ( 4 6 ) ( 4 7 ) ( 4 8 ) 根据定义2 1 可知，满足( 4 5 ) 的d 一1 的个数为 + 2 ( 1 ，佗) ；相应的，满足( 4 5 ) 的d 的 个数也为九+ 2 ( 1 ，n ) 又由( 1 ) ，( 2 ) 得，满足( 4 6 ) ，( 4 7 ) 的d 的个数均为 + 1 ( 1 ，n ) 一f k + 2 ( 1 ，佗) 而满足( d ，仃) = ( d + 1 ，n ) = = ( d + k 一1 ，佗) = l 的d 的个数为a ( 1 ，凡) 所以，满足 ( 4 8 ) 的d 的个数为 ( 1 ，礼) 一 + 2 ( 1 ，n ) 一2 ( a + 1 ( 1 ，他) 一 + 2 ( a ，n ) ) = ( 1 ，7 , ) 一2 + 1 ( 1 ，n ) + a + 2 ( 1 ，n ) ， 即( 3 ) 成立 4 2 定理的证明 定理4 1 设n ，k 是给定正整数，对于i = 1 ，k ，若记满足a ( a ，扎) = ( 1 ，竹) 一k + i 的正整数o ( 1 a n ) 的个数为帆，n ( i ) ，则有： ( 1 ) u k m ( 1 ) + n k ，扎( 2 ) + + 帆，他( 惫) = 佗， ( 2 ) n k ，。( 1 ) = ，2 k 一2 ( 1 ，n ) ， ( 3 ) n k ，n ( t ) = t ( 丘一i 一1 ( 1 ，r 1 ) + y 2 k i + 1 ( 1 ，几) 一2 ，2 一i ( 1 ，n ) ) + 2 ( ，2 愚一 ( 1 ，佗) 一，2 七一i + 1 ( 1 ，扎) ) ，其 中2 i k 一1 】8 关于数论函数的一个问题 第四章 厶( 口，n ) 的进一步讨论 注由定理4 1 知，n k ，n ( 七) ：n 一譬帆，n ( i ) ；由定理2 1 可知，对给定的正整数k ， i = 1 可实效地确定n k ，n ( z ) ( 对每一个t ) 证明对于1 a 礼，存在唯一的i 使得 ( o ，n ) = f k ( 1 ，几) 一k + i ，且对于不同的i ， 使得前式成立的整数a 也不同，所以有n k 。( 1 ) + 眠，n ( 2 ) + + 帆，。( 惫) = 礼，即( 1 ) 成 立 由第三章注3 知，设正整数k ，7 , 给定，对于1 i k ，正整数a ( 1 o 佗) 满足 厶( n ，n ) = y k ( 1 ，t , ) 一惫+ i 营( 3 8 ) 中有且仅有k i 组数满足每组的连续k 个数均与r l , 互素 对于给定的正整数惫，n ，当i = 1 时，正整数a 满足 ( 口，n ) = ( 1 ，他) 一k + 1 兮( 3 8 ) 的k 一1 组数满足每组的连续k 个数均与礼互素，即a k + 1 ，a k + 2 ，a + k 一2 这连续2 k 一2 个数均与n 互素，此时注意到l a k + 1 ，n + k 一2 礼， 所以，1 a 竹，满足a ( n ，扎) = a ( 1 ，佗) 一k + 1 的a 与1 ，2 ，n 中连续2 k 一2 个与 n 互素的数一一对应 从而，1 a n ，满足y k ( a ，佗) = f k ( 1 ，佗) 一七+ 1 的a 的个数与1 ，2 ，7 , 中连续2 七一2 个与几互素的数的个数相同 由定义2 1 我们得，n k ，n ( 1 ) = f 2 k 一2 ( 1 ，n ) 对于给定的正整数k ，n ，当2 i 七一l 时，正整数a 满足厶( n ，n ) = f k ( 1 ，n ) 一后+ i 铮( 3 8 ) 中有且仅有连续的k i 组数，每组中连续k 个数均与n 互素