---
title: Euler phi Function
tags: crypto
lang: zh_tw
---

* [筆記總覽](https://hackmd.io/@LJP/rkerFdnqS)

[TOC]

# Euler's phi Function
> The Euler phi function (or Euler totient function) is defined by $\phi(n) = |\{x|1\leq x \leq n, x \perp n\}|$

簡單來說 $\phi(n)$ 就是 1 到 $n$ 中, 跟 $n$ 互質的數字的**數量**
(注意互質的定義是兩者的公因數為1，所以1跟所有正整數互質)

以下是比較重要的等式
1. $\phi(p) = p - 1$ (當 $p$ 是質數)
2. $\phi(p^k) = p^{k-1}(p-1)$
3. $\phi(mn) = \phi(m)\phi(n)$ (當 $m \perp n$ 且 $m,n$ 都是質數)

## Proof 1
$p$ 中跟 $p$ 不互質的就只有 $p$ 自己

## Proof 2
以 $p = 7, k = 2$ 為例, $7^2$ 中跟 $7^2$ 不互質的有
$7 \times 1, 7 \times 2, ..., 7 \times 7$
所以 $\phi(p^2) = p^2 - p = p(p - 1)$

現在繼續擴展, $k = 3$, 則 $7^3$ 中跟 $7^3$ 不互質的有
$7 \times 1, 7 \times 2, ..., 7 \times 7, ..., 7 \times 49$
所以 $\phi(p^3) = p^3 - p^2 = p^2(p - 1)$

最後能統整出
$\phi(p^k) = p^k - p^{k - 1} = p^{k - 1}(p - 1)$

## Proof 3
以 $m = 5, n = 7$ 為例, $5 \times 7$ 中跟 $5 \times 7$ 不互質的有
$5 \times 1, 5 \times 2, 5 \times 3, 5 \times 4$
$7 \times 1, 7 \times 2, 7 \times 3, ..., 7 \times 6$
$5 \times 7$
總共是 4 + 6 + 1 個, 所以 $\phi(5 \times 7) = (5 \times 7) - (5 - 1) - (7 - 1) - 1$

統整後得到
$$
\begin{split}
\phi(mn) &= mn - (m - 1) - (n - 1) - 1\\
&= mn - m - n + 1 \\
&= (m - 1)(n - 1) \\
&= \phi(m)\phi(n)
\end{split}
$$