For which n is it true that $\phi(n^2)=\phi(n)+10$

Question

For which $n$ is it true that $\phi(n^2)=\phi(n)+10$?

$\phi(n)$ is defined as the totient function, i.e., all positive integers up to $n$ that are relatively prime to $n$. While that definition makes sense, I have no idea how to deal with $\phi(n^2)$ and consequently the question. Do I just start plugging and checking all numbers above $10$ to notice a pattern?

There is probably a better way to do this, I think, and I would appreciate any help. Thank you!

Answer 1

Hint $\phi(n)$ is a divisor of $\phi(n^2)$.

Added Since $\phi(n)| \phi(n^2)-\phi(n)$ we get $\phi(n)|10$ and hence $\phi(n)=1,2,5,10$

Next, in each of the four cases, using the equation and $\phi(n^2)=n \phi(n)$ you can find the value of $n$, which will be integer only in one of the four possible scenarios.

Answer 2

Use the following: if

$$n=\prod_{k=1}^np_k^{a_k} \,,\,\,p_k\;\text{ distinct primes}\;,\;\;a_k\in\Bbb N\implies\phi(n)=n\prod_{k=1}^n\left(1-\frac1p\right)\implies$$

$$\phi(n^2)=\phi(n)+10\implies n^2\prod_{k=1}^n\left(1-\frac1p\right)=n\prod_{k=1}^n\left(1-\frac1p\right)+10\iff$$

$$n\prod_{k=1}^n\left(1-\frac1p\right)\left[n-1\right]=10$$

That doesn't leave many options for $\;n\;$, as $\;n\prod\limits_{k=1}^n\left(1-\frac1p\right)\;$ ...In fact, the only possibilites are $\;n=2,3,6,11\;$

Answer 3

There's all sorts of formulas for $\phi(n)$. The one that makes the must sense and is easiest for me to remember is if $n = \prod p_i^{a_i}$ (where $p_i$ are distinct primes) then $\phi(n) = \prod (p_i-1)p^{a_i - 1}$

So $\phi(n^2) = \phi(n) + 10$

$\prod (p_i-1) \prod p_i^{2a_i - 1} = \prod (p_i-1)\prod p_i^{a_i - 1} + 10$

$\prod p_i^{2a_i - 1} = \prod p_i^{a_i - 1} + \frac {10}{\prod (p_i-1)}\in \mathbb Z$.

$\prod p_i^{a_i} = 1 + \frac {10}{\prod (p_i-1)\prod p_i^{a_i - 1}} \in \mathbb Z$.

That means $\prod p_i^{a_i} = 2,3, 6,11$

If $\prod p_i^{a_i} = 2$ then $n = 2^1$ and $\prod (p_i-1)\prod p_i^{a_i - 1} =10$. But $\prod (p_i-1)\prod p_i^{a_i - 1} = 1$.

If $\prod p_i^{a_i}=3$ then $n = 3^1$ and $\prod (p_i-1)\prod p_i^{a_i - 1} =5$. But $\prod (p_i-1)\prod p_i^{a_i - 1} =2$

If $\prod p_i^{a_i} = 6$ then $n = 2^13^1$ and $\prod (p_i-1)\prod p_i^{a_i - 1} =2$. And $\prod (p_i-1)\prod p_i^{a_i - 1} =2$

That's a possiblity: $\phi(6^2) = (2-1)2*(3-1)*3 = 12$ while $\phi(6) = (2-1)(3-2) = 2$.

If $\prod p_i^{a_i} = 11$ then $n = 11^1$ and $\prod (p_i-1)\prod p_i^{a_i - 1} =1$. But $\prod (p_i-1)\prod p_i^{a_i - 1} =10$.

So $n = 6$ is only solution.

Answer 4

Every prime that divides $n^2$ also divides $n$.

$\phi$ is multiplicative across different primes, and $\phi(p^k) = p^{k-1}\phi(p)$.

Taken all together, this means $\phi(n^2) = n\phi(n)$.

So...
$\begin{align} \phi(n^2) &=\phi(n)+10\\ \implies n\phi(n) &=\phi(n)+10\\ \implies (n-1)\phi(n) &= 10\\ \end{align}$

So $n{-}1 \mid 10$, which gives you a very limited set of values to trial.