1
$\begingroup$

I'm currently working in the following Euler's theorem exercise:

Let $n$ be a positive integer. Show that $n\phi(n)=\phi(n^2).$

Here are my thoughts:

If $n$ is prime, then

$$\phi (n^2) = n^2-n = n(n-1) = n \phi (n).$$

If $n$ is not prime and $p$ and $q$ are prime factors of $n,$ then

$$\phi (n^2) = (p^2-p)*(q^2-q)$$ $$\phi (n^2) =p(p-1)*q(q-1)$$ $$\phi (n^2) =p\phi(p)*q\phi(q)$$ $$\phi (n^2) =pq \phi(pq)$$ $$\phi (n^2) = n \phi(n)$$

Is that enough proof? Is there a more general one? Am I missing something? Any hint will be really appreciated.

$\endgroup$
  • 3
    $\begingroup$ That only deals with the case where $n=pq$. What if $n=p^2q$, $pqr$ etc.? $\endgroup$ – Lord Shark the Unknown Feb 3 at 5:17
  • $\begingroup$ $$\varphi(m)=m\prod_{p\mid m}\left(1-\frac{1}{p}\right)$$ and the primes dividing $m$ and $m^2$ are the same, so $\frac{\varphi(m)}{m}=\frac{\varphi(m^2)}{m^2}$. $\endgroup$ – Jack D'Aurizio Feb 3 at 13:27
4
$\begingroup$

More generally, let $n=p_1^{k_1}p_2^{k_2}...p_r^{k_r}.$ Then $$n^2=p_1^{2k_1}p_2^{2k_2}...p_r^{2k_r},$$ $$ \phi(n)=n(1-1/p_1)(1-1/p_2)...(1-1/p_r),$$and $\phi(n^2)=n^2(1-1/p_1)(1-1/p_2)...(1-1/p_r) = n \phi(n)$.

$\endgroup$
  • $\begingroup$ Even more generally $$\phi(n^m)=?$$ $\endgroup$ – lab bhattacharjee Feb 3 at 5:30
  • $\begingroup$ @labbhattacharjee asked for a more general formula than OP: $\phi(n^m)=n^{m-1}\phi(n)$ $\endgroup$ – J. W. Tanner Feb 3 at 5:33
  • $\begingroup$ In particular, when $n$ is prime, $ \phi (n^m)=n^{m-1} (n-1) $ $\endgroup$ – J. W. Tanner Feb 3 at 5:34
3
$\begingroup$

Or, without directly mentioning any of the prime factors:

The set of integers relatively prime to $n$ is exactly the same as the set of integers relatively prime to $n^2$ (because the same list of primes divide them). Also, $n+k$ is relatively prime to $n$ if and only if $k$ is. That gives us $\phi(n)$ relatively prime integers in $[1,n]$, $\phi(n)$ in $[n+1,2n]$, $\phi(n)$ in $[2n+1,3n]$, and so on up to $[(n-1)n+1,n^2]$. With $n$ disjoint sets of size $\phi(n)$, that's $n\cdot \phi(n)$ total integers relatively prime to $n$ (or $n^2$) in $[1,n^2]$. Done.

$\endgroup$
0
$\begingroup$

$\phi(n)=n\prod_{p_i|n}(1-\frac 1{p_i})$, so $n\cdot\phi(n)=n^2\prod_{p_i|n}(1-\frac 1{p_i})=n^2\prod_{p_i|n^2}(1-\frac 1{p_i})=\phi(n^2)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.