Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
Just try the 9 possible values of $x$... –  vonbrand Feb 11 at 19:25

4 Answers 4

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.

share|improve this answer
9  
Going mod 3 is slightly less work. –  Grumpy Parsnip Feb 11 at 18:10
    
@GrumpyParsnip: true. :). However, it doesn't take much time to do this calculation either- and can be generalized to problems involving other numbers. –  voldemort Feb 11 at 18:12
    
@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$ –  chubakueno Feb 11 at 18:13
1  
@chubakueno Then show that $\sqrt{2+3n}$ is never an integer –  Hagen von Eitzen Feb 11 at 18:16
    
Ok, so proving mod 3 sufficient? –  user127992 Feb 11 at 18:26

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

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

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

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.