1
$\begingroup$

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.

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

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

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