# find the solutions of $\phi(n) = 14$.

I tried the following.

Let $n = \Pi p_i^{\alpha_i}$, be a prime factorization of $n$, Then we can see that:

$\phi(n) = \Pi(p_i^{\alpha_i} - p_i^{\alpha_i-1}) = 14 = 2\cdot7$.

The main problem here is that i don't know how to find $p_i$ such that the last equation does hold or not. Is there a trick in finding these solutions?

Kees

• If prime $p \mid n$, then $\phi(n) \ge p-1$, so the fact that $\phi(n) = 14$ limits the possible prime factors of $n$. – hardmath Sep 17 '15 at 15:25
• Since $14=2\cdot7$, you should find first a prime $p$ and an integer power $\alpha$ such that $p^{\alpha}-p^{\alpha-1}=p^{\alpha-1}(p-1)=2$ (and similarly another prime $p'$ and exponent $\alpha'$ for the second factor 7), but you have that $p-1=2/p^{\alpha-1}$ must be an integer and this restrict the possible choices of $p$ and $\alpha$... – PITTALUGA Sep 17 '15 at 15:40
• I imagine you saw that $n$ can have at most one odd prime divisor and so exactly one. – André Nicolas Sep 17 '15 at 15:46
• Because $\varphi(p^k)$ is even for every odd prime $p$, and $14$ is not divisible by $4$. – André Nicolas Sep 17 '15 at 15:50
• Pretty soon your detective work should show there is no $n$ such that $\varphi(n)=14$. – André Nicolas Sep 17 '15 at 15:54

$$\phi(n)=\prod_{i=1}^m p_i^{\alpha_i-1}(p_i-1)=2\cdot 7\implies \exists p_i=7\ \mathrm{but}\ p_i-1=1\ \mathrm{or}\ 2$$ which leads to a contradiction, hence no such $n$ exists.

In fact, a little reflection reveals that $\phi(n)$ maybe square free only if $n$ is some power of a prime.

• How does $p_1 = 2$ follow? Wouldn't it be possible that $\alpha_1 = 1$? Then $p_1 = 3$ would be permissible. – Cloudscape Sep 17 '15 at 16:07
• You are correct, I have edited my answer. – Samrat Mukhopadhyay Sep 17 '15 at 16:11
• Sorry, I didn't understand contradiction, please help, And in the version of the problem, I read they also asked to verify that $14$ is the smallest integer with this property. Please add all these in our solution. – mnulb Dec 30 '16 at 17:22
• What I tried to say was that there must be one $p_i$ such that $p_i=7$, but what about $p_i-1$ then? From the equality we see that it must be either $1$ or $2$, which forces $p_i$ to be either of $2$ or $3$, and that begets a contradiction, as $p_i-1=6$. – Samrat Mukhopadhyay Dec 31 '16 at 8:02
• Also, I do not see the OP asking anything about showing that $14$ is the smallest "such" number, though I do not know what you mean by such as this equation is not satisfied by any $n$. – Samrat Mukhopadhyay Dec 31 '16 at 8:04

$2 \cdot7$ is the only non-trivial way to write $14$ as a product of two naturals.

Hence, you have to consider exactly the following cases ($p, q$ prime):

1.) $n = p^k$, i. e. $p^k - p^{k-1} = 14$

2.) $n = p^k q^m$, i. e. $p^k - p^{k-1} = 2 \wedge q^m - q^{m-1} = 7$

Case 1:

If $k = 1$, then $p^k - p^{k-1} = 14$ has the solution $p=15$, which is not prime. If $k \ge 2$, $14$ must divide the prime or $p - 1$. $14|p$ is impossible. If $14|(p-1)$, then $p \ge 15$. But we have $p^k - p^{k-1} \ge p^2 - p$ (since $p^k - p^{k-1}$ grows if $k$ grows), and $$p^2 - p = p(p-1) \ge 15 \cdot 14 > 2.$$

Case 2:

Let's first determine $q$ and $m$. $m=1$ is impossible, since $q - 1 = 7$ has solution $q=8$, which is not prime. If $m \ge 2$, then $7$ must divide either $q$ or $q-1$. $q = 7$ is impossible, since $7^k - 7^{k-1} \ge 49 - 7 > 7$.

We conclude that 14 is not in the image of $\phi$.