欧拉函数

Euler's totient function for a positive integer $n$ is defined as the number of relatively prime numbers to $n$ that are less than $n$. This is commonly denoted as $\phi(n)$. One important and useful property of this function is that it is multiplicative, meaning that if $m$ and $n$ are relatively prime, then $\phi(mn)=\phi(m)\cdot \phi(n)$.

However, this is not the only important thing about Euler's totient function; it also has a formula: If $n={p_1}^{e_1}{p_2}^{e_2}\cdots {p_k}^{e_k}$ where $p_1,p_2,...,p_n$ are primes, then $$\phi(n)=n\prod\limits_{j=1}^{k} (1-\frac{1}{p_j})$$$$=n(1-\frac{1}{p_1})(1-\frac{1}{p_2})\cdots (1-\frac{1}{p_k}).$$

In order to prove this statement, we can use two methods, PIE (Principle of Inclusion and Exclusion) or simple algebra and number theory. I'm going to show the latter; however, we will first prove a simple fact:

If $n=p^e$, then $\phi(n)=p^e(1-\frac{1}{p})$. This is very simple to prove. If $p$ is the only prime factor of $n$, then the numbers that are not relatively prime with $n$ (not including $1$ since $1$ is relatively prime to every number) are $$p, 2p, 3p, ..., (p^{e-1}-1)p, (p^{e-1})p.$$ Clearly, there are $p^{e-1}$ numbers less than or equal to $n$ that are not relatively prime to $n$. Hence, the total number of relatively prime numbers less than or equal to $n$ is $$p^e-p^{e-1}=p^e(1-\frac{1}{p}).$$

Now time for the real proof. Let $n={p_1}^{e_1}{p_2}^{e_2}\cdots {p_k}^{e_k}$ where $p_1,...,p_k$ are prime. Because the totient function is multiplicative, we can express $$\phi(n)=\phi({p_1}^{e_1}{p_2}^{e_2}\cdots {p_k}^{e_k})$$$$=\phi({p_1}^{e_1})\phi({p_2}^{e_2})\cdots \phi({p_k}^{e_k}).$$ Using what we just proved in the above paragraph, we can substitute $$\phi({p_1}^{e_1})={p_1}^{e_1}(1-\frac{1}{p_1}),$$$$\phi({p_2}^{e_2})={p_2}^{e_2}(1-\frac{1}{p_2}),$$ and so on. Substituting these in and rearranging the terms, we get $$\phi({p_1}^{e_1})\phi({p_2}^{e_2})\cdots \phi({p_k}^{e_k})$$$$={p_1}^{e_1}{p_2}^{e_2}\cdots {p_k}^{e_k}(1-\frac{1}{p_1})(1-\frac{1}{p_2})\cdots (1-\frac{1}{p_k})$$ and since $n={p_1}^{e_1}{p_2}^{e_2}\cdots {p_k}^{e_k}$, we arrive at $${p_1}^{e_1}{p_2}^{e_2}\cdots {p_k}^{e_k}(1-\frac{1}{p_1})(1-\frac{1}{p_2})\cdots (1-\frac{1}{p_k})$$$$=n(1-\frac{1}{p_1})(1-\frac{1}{p_2})\cdots (1-\frac{1}{p_k})$$ which is exactly what we want. Although we now know a formula, sometimes directly using the property that $\phi(n)$ is multiplicative is faster when computing $\phi(n)$.

However, what is this function used for? One theorem it is used in is Euler's Theorem. Although I won't prove it (see Asif E Elahi's explanation on totient functions for a proof), it says that for any positive integer $a$ and $n$ that are relatively prime, $$a^{\phi(n)}\equiv 1 \pmod{n}.$$ This is quite useful and we can quickly verify Fermat's Little Theorem, which states that for any $p\nmid a$ where $p$ is prime and $a$ is a positive integer, $$a^{p-1} \equiv 1\pmod{p}.$$ Plugging $a$ and $p$ into Euler's theorem (which is legal since $a$ and $p$ are relatively prime), we get $$a^{\phi(p)}\equiv 1\pmod{p}$$ and since $\phi(p)=p-1$ (this is easy to notice), we get exactly what Fermat's Little Theorem says.

Totient Function

Definition: For a positive integer $n$, $\phi(n)$ is the number of positive integers which are less or equal to $n$ and relatively prime to $n$.For example $\phi(10)=4$ as there are $4$ positive integers $1,3,7,9$ which are less or equal to $10$ and relatively prime to $10$.

Theorem: Let $n$ be a positive integer. Then for all positive integer $a$ with $\gcd(a,n)=1$ $$a^{\phi(n)}\equiv1\pmod n$$ Proof: Let $r_1,r_2,..........r_{\phi(n)}$ be the positive integers that are less than $n$ and relatively prime to $n$. Now we consider the numbers $ar_1,ar_2,..............ar_{\phi(n)}$. We prove that $$\{ar_1,ar_2,..............ar_{\phi(n)}\} \equiv \{r_1,r_2,..........r_{\phi(n)}\}\pmod n$$ in some order. As $(a,n)=1$ and $\gcd(r_i,n)=1$, we must have $\gcd(ar_i,n)=1$ for $1\leq i\leq \phi(n)$. Now if there exists distinct $i$ and $j$ s.t $ar_i\equiv ar_j \pmod n$ then we can divide both sides by $a$ as $(a,n)=1$ to get $r_i\equiv r_j \pmod n$ which is impossible.

So all the numbers $ar_{1},ar_{2}.........ar_{\phi(n)}$ are relatively prime to $n$ and leave different residues when divided by $n$.

So $$\{ar_1,ar_2,..............ar_{\phi(n)}\} \equiv \{r_1,r_2,..........r_{\phi(n)}\}\pmod n$$ in some order. Now we can deduce $$(ar_1)(ar_2).........(ar_{\phi(n)}) \equiv r_1r_2.........r_{\phi(n)}\pmod n$$ Hence $a^{\phi(n)}r_1r_2..........r_{\phi(n)} \equiv r_1r_2..........r_{\phi(n)} \pmod n$

Cancelling $r_1r_2..........r_{\phi(n)}$ from both sides, we finally get $a^{\phi(n)}\equiv 1 \pmod n$

$\textbf{Euler's Phi function}$

Euler's Phi function,also known as totient function for a positive integer $n$ , denoted as $\varphi(n)$, is the number of positive integers less than $n$ which are coprime to $n$.

As per Mathematical definition, $\varphi(n)$ the number of integers $k$ such that

(i) $k <n$ and $\quad\quad\quad$(ii) $gcd(k,n)=1$.

**1 is always counted in $\varphi(n)$ **.

$\bullet\quad$As per this definition as we know that prime numbers are coprime to all integers less than itself, we conclude $$\varphi(p)=p-1$$ when $p$ is a prime number.

$\bullet\quad$If $a$ and $b$ are coprime, then $$\varphi(a\times b)=\varphi(a) \times \varphi(b)$$

$\bullet\quad$ $\varphi$ of power of a prime, is $$\varphi(p^k)= p^{k-1}(p-1)$$

$\bullet\quad$ To find the value of $\varphi(n)$, the formula is $$\varphi(n) = n \prod_{p\mid n} \biggl( 1 - \dfrac{1}{p} \biggr)$$

Illustrative examples:-

$(i)\quad\varphi(14)\\ = \varphi(2\times 7) \\ = 1\times 6 = \boxed{6}$

$.\\.\\ (ii) \quad \varphi(72) \\ = \varphi(9\times 8) \\ = \varphi(9) \times \varphi(8) \\ = \varphi(3^2) \times \varphi(2^3) \\ = (3^1\times 2) \times (2^2\times 1) = \boxed{24}$

$.\\.\\ (iii) \quad \varphi(2014)\\ = \varphi(2\times 19\times 53) \\= 2014\times \biggl(1 -\dfrac{1}{2}\biggr)\biggl(1 -\dfrac{1}{19}\biggr)\biggl(1 -\dfrac{1}{53}\biggr)\\ =2014\times \dfrac{1}{2} \times \dfrac{18}{19}\times \dfrac{52}{53}\\ = 1\times 18\times 52 \\ \bigl(=\varphi(2) \varphi(19)\varphi(53) \bigr) =\boxed{936}$

Prove that $$\varphi(n)=\prod_{p^e||n}p^{e-1}(p-1).$$