剑锋所指,心之所向。

本文部分翻译自 Euler's Phi Function and the Chinese Remainder Theorem

今天讲数论的时候,提到了这个,上 wiki 搜了一下发现了这个文章。

一些约定

  • \land 为逻辑且。

问题引入

试证明欧拉函数 \varphi 是一个积性函数。形式化的来讲:

试证明对于 \forall m \bot n,都有

\varphi(mn) = \varphi(m) \times \varphi(n)

证明

我们试图通过构造若干个集合来证明。

令集合 A = \{x \mid 1 \leq x \leq m \land x \bot m \}

令集合 B = \{x \mid 1 \leq x \leq n \land x \bot n \}

令集合 C = \{x \mid 1 \leq x \leq mn \land x \bot mn\}

此时命题归约为证明 |A \times B| = |C|。也就是说,证明存在一个映射 f: C \mapsto A \times B,满足 f 为双射。

A \times B 表示 A, B 的笛卡尔积,定义为:A \times B = \{(x, y) \mid x \in A \land y \in B\}

我们尝试给这个映射 f 一些性质。

对于任意的 k \in C,令 (x, y) = f(k),我们要求 (x, y)k 满足:

k \equiv x \pmod m \land k \equiv y \pmod n

倘若 f 为一个双射,命题成立。

先证 f 为一个满射。

采用反证法,假设 f 不是一个满射,则必定存在 (x, y),使得 \forall a \in C,都有 f(a) \neq (x, y)。这意味着关于 a(a \in C) 的方程

\begin{cases}a \equiv x \pmod m \\a \equiv y \pmod n\end{cases}

无解。

将方程转变一下形式

\begin{cases}k_1m + x = a \\k_2n + y = a\end{cases}

即:

k_1m - k_2n = x + y

无解。

然而,由于 \gcd(k1, k2) = 1,根据裴属定理可以得到,该方程一定有解。

因此,可以导出矛盾。

当然,通过中国剩余定理也可以更快地导出矛盾。

再证 f 为一个单射。

亦采用反证法,假设 f 不是一个单射,则存在 a,使得在 A 集合中不存在 a \bmod mB 集合中不存在 a \bmod n

然而容易发现任何数 \bmod m 都会落在 A 集合中。故不存在 a \bmod m \not\in AB 集合同理。

因此,导出矛盾。

所以 f 既为单射,也为满射,故为双射。

因此,集合 A \times BC 存在一一对应的关系。

|A \times B| = |C|

Q.E.D.

莫比乌斯函数的应用与莫比乌斯反演
上一篇 «
树链剖分做题记录
» 下一篇