0

How can I show this for Euler's $\phi$ function? $$\phi(n^2) = n\,\phi(n)$$

Ive been struggling a lot with this problem, I would appreciate some help.

Blue
  • 75,673
x3la.F
  • 119
  • Try an example, such as $n=6$. Can you list the coprime numbers for $6$ and $36$ and then spot the pattern? – Henry Jul 04 '22 at 15:09
  • Can you show $\text{hcf}(n,k)=1 \iff \text{hcf}(n^2,k)=1$? [$\text{gcd}$ if you prefer that notation] – Henry Jul 04 '22 at 15:11
  • 1
    Euler's product formula implies that $\frac{\phi(n^2)}{n^2} = \frac{\phi(n)}{n}$ because $n^2$ and $n$ have exactly the same prime factors. – lhf Jul 04 '22 at 15:13
  • Hint: First remember, for prime $p$, $\phi (p^k)=(p-1)(p^{k-1})$. Prove the property for prime powers, and then recall the fact that $\phi$ is a multiplicative function. – Keith Backman Jul 04 '22 at 15:19

2 Answers2

5

$\begin{align}\frac{\varphi(n^2)}{n^2}&=\Pi_{p|n^2} (1-\frac{1}{p})\\&=\Pi_{p|n} (1-\frac{1}{p}) \\&=\frac{\varphi(n) }{n}\end{align} $

Note : $p|n^2=n\cdot n$ implies $p|n$ . Hence $p|n^2$ iff $p|n$

Sourav Ghosh
  • 12,997
0

Remember, $\phi(n)$ counts the integers $1\le k\le n$ coprime to $n$.

Consider $\phi(n^2)$. For any $1\le k\le n^2$, we can divide $k$ by $n$ to write $k=nq+r$ (with $q$ the quotient $0\le q<n$ and $r$ the remainder $0\le r<n$). Note $k$ coprime to $n^2$ iff it's coprime to $n$, iff $k-qn=r$ is coprime to $n$. Thus, there are $n\phi(n)$ different $k$s we're counting, where $n$ is the number of options for $q$ and $\phi(n)$ is the number of options for $r$. Therefore, $\phi(n^2)=n\phi(n)$.

anon
  • 151,657