Using Euler's Totient identity to deduce an equality

Question

$ϕ(m · n) = \frac{ϕ(m) · ϕ(n) · gcd(m, n)}{ϕ(gcd(m, n))}$

Deduce from the previous identity that $ϕ(n^k) = n^{k−1}· ϕ(n)$

I know that \begin{eqnarray*} \phi(m) = m \prod_{p \mid m } (1-\frac{1}{p}). \\ \end{eqnarray*}

How can I make use of it?

Answer 1

You are given the identity

$$\phi(m \cdot n) = \frac{\phi(m) \cdot \phi(n) · \gcd(m, n)}{\phi(\gcd(m, n))} \tag{1}\label{eq1A}$$

and are asked to deduce from this that

$$\phi\left(n^k\right) = n^{k−1} \cdot \phi(n) \tag{2}\label{eq2A}$$

You mention, and ask how to make use of, the relation of

$$\phi(m) = m \prod_{p \mid m } \left(1-\frac{1}{p}\right) \tag{3}\label{eq3A}$$

However, the question asks you to only use \eqref{eq1A}. You don't need to use, nor should you use, \eqref{eq3A}. Instead, assume $n$ is any positive integer and set $m = n^{k-1}$ for any integer $k \ge 1$ in \eqref{eq1A} to get

$$\phi\left(n^k\right) = \frac{\phi\left(n^{k-1}\right)\phi(n)\gcd\left(n^{k-1},n\right)}{\phi\left(\gcd\left(n^{k-1},n\right)\right)} \tag{4}\label{eq4A}$$

There are $2$ basic cases cases to consider. First, if $k = 1$, then $n^{k-1} = 1$ so $\gcd\left(n^{k-1},n\right) = 1$ and \eqref{eq4A} becomes

$$\phi(n) = \frac{\phi(1)\phi(n)}{\phi(1)} = \phi(n) \tag{5}\label{eq5A}$$

Note this matches \eqref{eq2A} for $k = 1$. Next, consider $k \gt 1$. Then $\gcd\left(n^{k-1},n\right) = n$ and \eqref{eq4A} becomes

$$\phi\left(n^k\right) = \frac{\phi\left(n^{k-1}\right)\phi(n)n}{\phi(n)} = n\phi\left(n^{k-1}\right) \tag{6}\label{eq6A}$$

You can see that with $k = 2$, \eqref{eq6A} becomes $\phi\left(n^2\right) = n\phi(n)$, which matches \eqref{eq2A}. Next, using the previous relation, plus $k = 3$ in \eqref{eq6A}, you get $\phi\left(n^3\right) = n\phi\left(n^2\right) = n\left(n\phi(n)\right) = n^2\phi(n)$, which also matches \eqref{eq2A}. Using this procedure with mathematical induction on $k$ in \eqref{eq6A}, you can quite easily prove \eqref{eq2A} is true for all positive integers $k$ and $n$. I'll leave this last part to you to do.

Answer 2

Well, if you are given

$ϕ(m · n) = \frac{ϕ(m) · ϕ(n) · gcd(m, n)}{ϕ(gcd(m, n))}$

Then let $m = n^{k-1}$ and $n= n$.

Thne $\phi (n^k) = \frac {\phi (n^{k-1})\phi(n)\gcd(n^{k-1},n)}{\phi(\gcd(n^{k-1},n))} =$

$\frac {\phi(n^{k-1})\phi(n)n}{\phi(n)} = \phi(n^{k-1})n$.

And this should tell us we can do this by induction:

For $k =1$ we have $\phi(n^1)= n^0\phi(n)$.

And if for $k=m$ we knew that $\phi(n^m)= n^{m-1}\phi(n)$.

Then for $k =m+1$ we would know that $\phi(n^{m+1}) = \phi(n^{m+1-1)n$

$=\phi(n^m)*n = n^{m-1}\phi(n)*n = n^m\phi n= n^{(m+1)-1}\phi(n)$.

ANd thus it follows by induction.

.....

Of course you need to prove

$ϕ(m · n) = \frac{ϕ(m) · ϕ(n) · gcd(m, n)}{ϕ(gcd(m, n))}$

in the first place