每周数论--欧拉φ函数与中国剩余定理

小糯米 · 2019-12-14 08:59:53 · 个人记录

欧拉公式

是一个十分神奇的公式。然而，除非找到计算φ（m）的有效方法，否则这个公式只能成为一个只具有观赏价值的饰品。因此本周我们讨论φ(m)的计算方法，并由此衍生出一个重要到不能再重要的定理--中国剩余定理。

首先，有一个公式是显然的，那便是当p为素数时，可以得出：

φ(p)=p-1。

下面我们来讨论当m=p^k时欧拉函数的计算。我们采用一种十分笨的方法：

计数。

当然，我们不会去设法数出与p^k互素的元素个数，而是先设法数出与p^k不互素的元素个数，然后减去就可以了。

那么问题来了，与p^k不互素的有哪些元素呢？其实很容易解决，因为p是素数，因此与p^k不互素的只有

p,2p,3p...(p^{k-1}-1)p,p^k。

不难数出，它们有p^{k-1}个，这样，我们就得出公式：

φ(p^k)=p^k-p^{k-1}

恭喜！我们已经完成了任务的一半！因为欧拉函数公式包含了一下两个内容：

1）：φ(p^k)=p^k-p^{k-1}。

2）：如果gcd(m,n)=1，那么φ(mn)=φ(m)φ(n)。

我们已经成功的证明完了第一条定理成立，那么第二条定理我们将如何证明呢？我们不妨再次尝试一下上文所提到的计数法。

那么，我们将如何计数呢？很简单，找到一个φ(mn)的集合一，再找到一个φ(m)φ(n)的集合二，然后证明这两个集合包含相同数量的元素即可。

那么，第一个集合是什么呢？我们可以将其表示为

{1≤a≤mn,gcd(a,mn)=1}

很明显，这里共有φ(mn)个元素，因为这就是它的定义。对于第二个集合，我们有

{1≤b≤m,gcd(b,m)=1;1≤c≤n,gcd(c,n)=1}

那么第二个集合包含了多少个集合对(b,c)呢？对于b，我们有φ(m)个选择，因为这正好是φ(m)的定义。对于n也是同理。根据乘法原理，我们就不难得出，集合对的数量刚好就是b与c数量的乘积，即φ(m)φ(n)。

这样，我们需要做的，就是从集合一中取出一个数a，使其满足

a≡b(mod m) a≡c(mod n)

也正是因此，我们需要证明以下两个陈述成立：

1）：集合一的不同数包含集合二的不同序对。

2）：集合二的每个序对适应集合一的某个数。

要验证断言一成立，我们不妨在集合一中取两个数a_1,a_2，并假设他们在集合二中有相同的项，我们把它转化成数学语言，就是

换句话说，a_1-a_2是可以被m、n整除的，然而我们又知道，m、n又都是互素的数，因此a_1-a_2必然被mn整除，再次转化成数学语言，就是

这样我们就得知，a_1,a_2一定是同一个数，这样断言一就被证明了。

那么断言二我们该如何证明呢？我们先用人话将它翻译一下，就是：

对于b和c任意已知值，至少可以求得一个数x，使得

x≡b(mod m) x≡c(mod n)

有没有觉得很熟悉？

没错！这就是中国剩余定理！

虽然很多OIer已经知晓了定理的内容，但为了便于证明，我还是不厌其烦的再将其内容陈述一下吧：

设m,n是整数，且gcd(m,n)=1，b和c是任意整数，则同余式组

x≡b(mod m) x≡c(mod n)

恰好有一个解0≤x≤mn。

那么我们就按照程序走，先解一下第一个同余式，其解一定是形如x=my+b的，我们将其带进第二个同余式里，即

my≡c-b(mod n)

由于gcd(m,n)=1，根据线性同余式定理，只有一个解使得同余式成立，我们把它设为y_1，将y_1乘m就得到了x，这样我们就完成了中国剩余定理的证明。

然后欧拉定理我们就证完啦。

QwQ