# For any number $n \gt 1$ and all of its prime divisor $d_1, d_2, …$ s.t. $d_i \equiv 1 \pmod 3$ for each $i$, show:

For any number $n \gt 1$ and all of its prime divisors $d_1, d_2, ...$ s.t.

$d_i \equiv 1 \pmod 3$ for each $i$

Show that the euler phi function $\phi(x) = 2n$ has no natural number solution.

• You mean: numbers $n$ such that all prime divisors of $n$ are congruant to $1$ modulo $3$? – Marc van Leeuwen Oct 17 '12 at 10:16

Let $x = \prod_{i=1}^n p_i^{\alpha_i}$ ($p_i$ the distinct prime factors of $x$) be given, we have $\phi(x) = \prod_{i=1}^n p_i^{\alpha_i - 1}(p_i - 1).$ So in order to have $\phi(x) = 2n$ with $n$ odd (as above) and $p_i - 1$ being even for all primes but 2, we see that $x$ must be of the form $x = 2^\alpha p^\beta$ with $\alpha \in \{0,1\}$. Then $\phi(x) = p^{\beta - 1}(p-1).$ This equals $2n = 2d_1\ldots d_r$ if (after reordering the $d_i$) $p-1 = 2d_1$ (or $=2$), $p^{\beta - 1} = d_2 \cdots d_r$. So $p = d_2 = \cdots = d_r$, and $2d_1 + 1 = p$. But $d_1 \equiv 1\pmod 3$, so $2d_1 + 1 \equiv 0 \pmod 3$. But $p$ is prime, so we must have $p-1 = 2$, all $d_i$ equval $p$. But then $p = 3$, which contradicts $p = d_1 \equiv 1 \pmod 3$. So $n$ can't have any prime divisors, contradicting $n > 1$.
So there is no such $x$.