3
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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$. $\endgroup$ – hardmath Sep 17 '15 at 15:25
  • 1
    $\begingroup$ 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$... $\endgroup$ – PITTALUGA Sep 17 '15 at 15:40
  • 1
    $\begingroup$ I imagine you saw that $n$ can have at most one odd prime divisor and so exactly one. $\endgroup$ – André Nicolas Sep 17 '15 at 15:46
  • 1
    $\begingroup$ Because $\varphi(p^k)$ is even for every odd prime $p$, and $14$ is not divisible by $4$. $\endgroup$ – André Nicolas Sep 17 '15 at 15:50
  • 2
    $\begingroup$ Pretty soon your detective work should show there is no $n$ such that $\varphi(n)=14$. $\endgroup$ – André Nicolas Sep 17 '15 at 15:54
3
$\begingroup$

$$\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.

$\endgroup$
  • $\begingroup$ How does $p_1 = 2$ follow? Wouldn't it be possible that $\alpha_1 = 1$? Then $p_1 = 3$ would be permissible. $\endgroup$ – Cloudscape Sep 17 '15 at 16:07
  • $\begingroup$ You are correct, I have edited my answer. $\endgroup$ – Samrat Mukhopadhyay Sep 17 '15 at 16:11
  • $\begingroup$ 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. $\endgroup$ – mnulb Dec 30 '16 at 17:22
  • $\begingroup$ 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$. $\endgroup$ – Samrat Mukhopadhyay Dec 31 '16 at 8:02
  • $\begingroup$ 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$. $\endgroup$ – Samrat Mukhopadhyay Dec 31 '16 at 8:04
1
$\begingroup$

$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$.

$\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.