证明欧拉函数

realnumber

正整数$a=p_1^mp_2^np_3^l....$,（$a$的标准分解式）,那么小于$a$且与$a$互素的正整数个数为$φ(a)$个,$φ(a)=p_1^{m-1}(p_1-1)p_2^{n-1}(p_2-1)p_3^{l-1}(p_3-1)....$

谷歌涂鸦中，融入了莱昂哈德·欧拉的许多数学成就，如三角学、欧拉函数和欧拉方程等。
莱昂哈德·欧拉（Leonhard Euler ，1707年4月15日～1783年9月18日）
又google涂鸦中，第三个字母O中图形指？

其妙

《初等数论》教材

realnumber

回复 2# 其妙
晓得，只是想把自己探索过程写下，
以下，$p,q$为素数,$m,n,a,$为正整数.
1.先尝试了下$φ(p)=p-1$，这个简单.
2.再$φ(p^m)$
3.$φ(pq)$
4.$φ(p^mq^n)$
5.$φ(pa)$,其中$(p,a)=1$
6.$φ(p^ma)$,改为尝试$φ(pa)$，其中分$(p,a)=1$,与$(p,a)=p$.

Infinity

欧拉曾研究刚体定点转动，使用笛卡尔坐标系很不方便，为此引入了欧拉角。估计指的就是这个。

至于欧拉函数$\varphi(x)$，只需证明它是积性函数，再注意到素数与小于自己的正整数都互素，就能迅速得到上述一般公式。

白兔糖

这个证法有很多，容斥原理的也有，中国剩余定理的也有，等等

hbghlyj

Infinity 发表于 2018-2-11 08:44
只需证明它是积性函数，再注意到素数与小于自己的正整数都互素，就能迅速得到上述一般公式。

MathCircle

hbghlyj

Lemma.$$\sum_{d \mid n} \phi(d)=n$$

Proof

Considering the set of fractions $\left\{\frac{1}{n}, \frac{2}{n}, \ldots, \frac{n-1}{n}, \frac{n}{n}\right\}=\left\{\frac{a_{1}}{b_{1}}, \frac{a_{2}}{b_{2}}, \ldots, \frac{a_{n-1}}{b_{n-1}}, \frac{a_{n}}{b_{n}}\right\}$ where $\left(a_i, b_i\right)=1$.
The set $\mathcal{D}$ of all denominators $\left\{b_i\right\}$ is precisely the set of all divisors of $n$.
Given a divisor $d$ of $n$, $d$ appears in the set $\mathcal{D}$ exactly $\varphi(d)$ times:
$$
\frac{a_i}{b_i}=\frac{a_i}{d}=\frac{a_i \frac{n}{d}}{n},
$$
where $\left(a_i, d\right)=1$ and $1 \leq a_i \leq d$.
Counting the elements in $\mathcal{D}$ in two different ways implies $n=\sum_{d \mid n} \varphi(d)$.

Möbius Inversion formula immediately gives
$$\phi(n)=\sum_{d \mid n} \mu(d) \frac{n}{d}$$
Debanjana Kundu

hbghlyj

白兔糖 发表于 2018-2-19 16:50
容斥原理的

引理 设 \(n\ge2\text{,}\) \(k\ge1\text{,}\) 并设 \(p_1,p_2,\dots,p_k\) 为不同素数，每个素数都整除 \(n\)。那么 \(\{1,2,\dots,n\}\) 中可被每个素数$p_i$整除的整数个数=\(
\frac{n}{p_1p_2\dots p_k}.
\)
由上述引理和容斥原理得出：
\begin{align*}
\phi(n) &= n-\sum\frac{n}{p_i}+\sum\frac{n}{p_ip_j}-\sum\frac{n}{p_ip_jp_k}+\dots\\
& =n \frac{p_1-1}{p_1}\frac{p_2-1}{p_2}
\frac{p_3-1}{p_3}\cdots.
\end{align*}

hbghlyj

白兔糖 发表于 2018-2-19 16:50
中国剩余定理的也有，

$n=\prod_i p_i^{\alpha_i}$
中国剩余定理 $\Bbb Z/(n)\,\cong\, \prod_i\Bbb Z/(p_i^{\alpha_i})$ 两个环同构，所以单位元素群同构。
利用“乘积环的一个元素是一个单位$\Leftrightarrow$其所有坐标都是单位”，计算两边的单位个数得$\varphi (n)=\prod_i\varphi \left (p_i^{\alpha _i}\right )$.