2
$\begingroup$

I'm trying to show the equation

$$x^2 \equiv 2 \mod 9$$

has no solutions, and I thought the best way might be to show that $\sqrt{2 + 9n}$ can never be an integer (for integer $n$). What might be a good way too go about this?

I've tried a proof by contradiction similar to the proof that $\sqrt{2}$ is irrational but can't seem to find a way to arrive upon the contradiction.

$\endgroup$
  • 1
    $\begingroup$ Just try the 9 possible values of $x$... $\endgroup$ – vonbrand Feb 11 '14 at 19:25
  • $\begingroup$ $2$ is not a quadratic residue mod $3$... $\endgroup$ – Watson Nov 22 '18 at 20:26
10
$\begingroup$

Hint any $x$ can be written as $9k$ or $9k+1$,or, ..., $9k+8$. Now square each of these numbers, and show that the remainder is never 2.

$\endgroup$
  • 10
    $\begingroup$ Going mod 3 is slightly less work. $\endgroup$ – Cheerful Parsnip Feb 11 '14 at 18:10
  • $\begingroup$ @GrumpyParsnip: true. :). However, it doesn't take much time to do this calculation either- and can be generalized to problems involving other numbers. $\endgroup$ – voldemort Feb 11 '14 at 18:12
  • $\begingroup$ @GrumpyParsnip But $(3k+r)^2=9k^2+6kr+r^2=3k(3k+2r)+r^2$...I don't see how this can help $\pmod 9$ $\endgroup$ – chubakueno Feb 11 '14 at 18:13
  • 1
    $\begingroup$ @chubakueno Then show that $\sqrt{2+3n}$ is never an integer $\endgroup$ – Hagen von Eitzen Feb 11 '14 at 18:16
  • $\begingroup$ Ok, so proving mod 3 sufficient? $\endgroup$ – user127992 Feb 11 '14 at 18:26
2
$\begingroup$

Suppose it was an integer. Then you have that for some $k\in\mathbb{N}$,

$$\sqrt{2+9n} = k$$

Or equivalently

$$k^2=9n+2.$$

Or

$$n = \frac{1}{9}(k^2+2).$$

Can you show that this can never hold (that is, $k^2+2$ is never divisible by $9$)?

Hint: notice this cannot work if $k$ is even so $k$ must be odd. If $k$ is odd, then $k = 2l+1$ for some integer $l$. Thus, you want to inspect what happens to $k^2+2 = 4l^2+4l+3$.

$\endgroup$
  • 2
    $\begingroup$ Saying that 2+9n is a square isn't the same as saying that it is n-squared. $\endgroup$ – Roger Feb 11 '14 at 18:07
  • 1
    $\begingroup$ Is it mentioned anywhere that the square root is $n$ itself ? $\endgroup$ – lsp Feb 11 '14 at 18:07
  • 2
    $\begingroup$ why $=n^2$? I should say $=k^2$. $\endgroup$ – drhab Feb 11 '14 at 18:07
  • $\begingroup$ Oh haha. My bad. Let me fix that. $\endgroup$ – Cameron Williams Feb 11 '14 at 18:14
  • $\begingroup$ I don't know how I did that. It's fixed now. $\endgroup$ – Cameron Williams Feb 11 '14 at 18:21
1
$\begingroup$

Hint $\, $ mod prime $\,p = 4n\!+\!3\!:\,\ \color{#0a0}{{-}1 \equiv x^2}\,\Rightarrow\, \color{#c00}{-1} \equiv (\color{#0a0}{-1})^{2n+1}\! \equiv (\color{#0a0}{x^2})^{2n+1}\! \equiv x^{p-1} \equiv \color{#c00}1,\,$ by little Fermat. Hence $\,p\mid 2 = \color{#c00}{1-(-1)},\,$ contra $\,p\,$ odd. Yours is the special case $\,n=0,\,\ p=3\,\, $ which, more simply, can be verified directly: $\,{\rm mod}\ 3\!:\ x\not\equiv 0\,\Rightarrow\,x\equiv \pm1\,\Rightarrow\, x^2\equiv 1.$

$\endgroup$
1
$\begingroup$

The nice thing about modulo equations, that you can just try all the possible solutions.

Mod 9 we have:

$$0^2\equiv1\\1^2\equiv1\\2^2\equiv4\\3^3\equiv0\\4^2\equiv7\\5^2\equiv7\\6^2\equiv0\\7^2=4\\8^2=1$$ $x$ nust be equal to one of them, And no square of them is 2.

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