1
$\begingroup$

Show that there are infinitely many positive integers $k$ such that the equation $\phi(n)=k$ has exactly two solutions, where $n$ is a positive integer.

Not entirely sure where to start or finish with this problem. I know that $\phi$ notation states that $\phi(n) = n(1-\frac{1}{p_1})(1-\frac{1}{p_2})\cdots(1-\frac{1}{p_S})$

but other than that I am lost.

$\endgroup$
  • $\begingroup$ Note that $\phi(p) = \phi(2p)$ if $p$ is prime. $\endgroup$ – B. Goddard Apr 13 '18 at 8:51
  • $\begingroup$ I remember another user asking this question yesterday, but I can't seem to find it now so presumably it has been deleted. (They cited it as being homework from some online source.) Is the question from a contest or something like that that is currently ongoing? $\endgroup$ – Dylan Apr 13 '18 at 11:03
  • $\begingroup$ That's actually kinda funny because I found it online too while looking for solutions for a previous homework assignment. I can provide the link to the problem(s) if need be. They're all actually pretty difficult for me to solve. It seems like it was an old homework problem for some university that the professor posted publicly. $\endgroup$ – CBsmith90 Apr 13 '18 at 11:57
  • $\begingroup$ @CBsmith90 The post yesterday included a hint to consider numbers of the form $k = 2 \times 3^{6m + 1}$. Not sure if that helps you. I can write out a full solution later. $\endgroup$ – Dylan Apr 13 '18 at 23:07
1
$\begingroup$

Let $k = 2 \times 3^{6m + 1}$. We claim that if $m > 0$, then $\phi(n) = k$ has exactly $2$ solutions. (For $m = 0$, it has four solutions: $7$, $9$, $14$, and $18$.)

Let $n = p_1^{a_1} p_2^{a_2} \cdots p_i^{a_i}$, where $p_j$ is a prime number, and $a_j$ is a positive natural number. Then $n$ is a solution if and only if $$ p_1^{a_1 - 1} p_2^{a_2 - 1} \cdots p_i^{a_i - 1} (p_1 - 1)(p_2 - 1) \cdots (p_i - 1) = k. $$

We note that if $n$ has at least two odd prime factors $p$ and $q$, then $(p - 1)(q - 1)$ is a factor of $\phi(n)$. Hence $4$ is a factor of $\phi(n)$, and sol $n$ is not a solution.

Thus any solution $n$ is of the form $n = 2^\alpha \cdot p^\beta$ where $p$ is some odd prime number, and $\alpha$ and $\beta$ are natural numbers, possibly equal to $0$. If $\alpha > 2$, then $\phi(8) = 4$ is a factor of $\phi(n)$, and so $n$ is not a solution. Thus $\alpha \in \{0, 1, 2\}$.

Suppose that $\alpha = 2$. Then if $\beta > 0$, we have that $2(p - 1)$ is a factor of $\phi(n)$, and so $4$ is a factor of $\phi(n)$, and so $n$ is not a solution. Thus if $\alpha = 2$, then $\beta = 0$, and so $n = 4$. But $\phi(4) = 2$ is not divisible by $3$, and so it is not equal to $2 \times 3^{6m + 1} = k$.

We thus must have that either $n = p^\beta$, or $n = 2 p^\beta$. In each case, we have that $$ \phi(n) = p^\beta - p^{\beta - 1}. $$

We thus must solve the equation $$ p^{\beta - 1} (p - 1) = 2 \times 3^{6m + 1}. $$

If $\beta = 1$, then this is equivalent to $p - 1 = 2 \times 3^{6m + 1}$. Not we note that $2 \times 3^{6m + 1} + 1 \equiv 2 \times 3 + 1 \equiv 0 \pmod 7$, and so this implies that $p = 7$. This corresponds to $m = 0$. We're considering the case where $m > 0$, so we can thus assume from now on that $\beta > 1$.

Since $\beta > 1$, we note that $p \mid 2 \times 3^{6m + 1}$, and so we have that $p = 3$. We thus must solve the equation $$ 2 \times 3^{\beta - 1} = 2 \times 3^{6m + 1}. $$ This clearly has the unique solution $\beta = 6m + 2$, and so the two solutions to the equation $\phi(n) = k$ are given by $n = 3^{6m + 2}$, and $n = 2 \times 3^{6m + 2}$.

$\endgroup$
  • $\begingroup$ Thank you for your input. However, I used a different value instead: $$2\times3^{4j+1}$$ Our work is pretty similar though so I guess either value works! $\endgroup$ – CBsmith90 Apr 18 '18 at 0:53

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.