2024年7月6日
模块：数论、容斥原理
难度：重要概念
问题引入：数论函数的莫比乌斯变换
【定义】数论函数
一个定义在正整数集上的实或复值函数 称作一个数论函数或算术函数。
显然欧拉函数就是一个数论函数.
欧拉函数的经典结论
欧拉函数有一个令人惊讶的经典结论：
证明：
只需将~按照与的最大公因数分类：
我们考察最大公因为的数：
由于,则
故恰为~中与互质的数，共个.（严格来讲，要说明双射）
所以有
最后一个等号用到因数的配对性.数论函数的莫比乌斯变换
事实上，是一个在数论中常见的操作.
【定义】莫比乌斯变换
若,则称是的莫比乌斯变换.
由上述欧拉函数结论知：经过莫比乌斯变换后就变为.
问题提出：那么知道如何求呢？
该过程也被称为“莫比乌斯反演”，其最终结果需要用到看着极为奇怪的莫比乌斯函数:反演公式如下
希望通过笔者的探索，让读者知晓该公式及的由来。问题分析
先做两个准备工作：
思考一：为求需不需要？
答案是否定的，若最终公式中出现一些，考虑,仅在唯一出现，无法用其他消去，导致矛盾！
思考二：线性表示唯一吗？
由思考一知，为求，我们只需考察，其中.
不妨设是的所有正因子.
由于的随意性，我们可将它们看作的基底，
下面说明之间是不可线性表示的：理由与思考一类似，仍然是反设后考虑最大的所对应的，过程略.
从最简单情形入手
下面正式开始探索(以下表示不同素数)
当时
当时
显然
到这里还看不出端倪，我们继续
当时
;
;
;
故
当时
类似的有
由其结构联想到：容斥原理！
对于更一般的，其中是个不同的素数，我们猜测形式与容斥原理类似：
证明
证明思路也与容斥原理完全一致，只需考察个体元素的贡献度：
考虑某个,显然
(i)若,则仅出现在中；
(ii)若,考虑其在中出现的次数为,结合符号共
综合知，最终成立
考虑一般情形中的简单情形
我们已经搞定素数指标至多为的情形，下考虑稍复杂的情形：
当时，
为抵消,必须有;
再考察后最终得
仔细观察该形式，它和前面情形有何联系？
是不是根据因子中的素因子个数？ 不是哇，不然去哪了？
而当我们根据简单情形的结构改写时会惊讶发现：
难道对一般的都成立？？？
再往下想一下就搞定了哇！
考虑一般的，我们对其因子的分类成不同集合：
仍然考虑单个因子：
若,则只在中出现一次.
若则考虑其指标减少的素数所在集合，不妨设.
易知,表明中包含1个;
类似的有,表明中包含1个
有表明中包含1个
。。。。。。
故在右侧的贡献度为：
综合(i)(ii),(*)证毕！
莫比乌斯函数及莫比乌斯反演公式
为简便表示上述反演过程，我们定义莫比乌斯函数：
若,则称是的莫比乌斯变换;
则已知反求的莫比乌斯反演公式如下：
如果觉得文章有价值，恳请您点个赞和在看！
欢迎后台交流！
往期精彩文章：
一、高联问题深度探究
简单又深刻！为什么立方数通常模7或9分析？——21高联B卷P4
观察大趋势，琢磨小细节——例谈离散不等式解题模式(23东南赛高一P7)
时刻观察特点，寻找思维捷径——丝滑分析2023中国女奥P6代数
二、强基自招
三、难题研究
组合零点定理（2）解北大“怀新一题”20230509期“数学家聚会”问题
////// END //////
