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 '14 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
10  
Going mod 3 is slightly less work. –  Grumpy Parsnip Feb 11 '14 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 '14 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 '14 at 18:13
1  
@chubakueno Then show that $\sqrt{2+3n}$ is never an integer –  Hagen von Eitzen Feb 11 '14 at 18:16
    
Ok, so proving mod 3 sufficient? –  user127992 Feb 11 '14 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 '14 at 18:07
1  
Is it mentioned anywhere that the square root is $n$ itself ? –  lsp Feb 11 '14 at 18:07
2  
why $=n^2$? I should say $=k^2$. –  drhab Feb 11 '14 at 18:07
    
Oh haha. My bad. Let me fix that. –  Cameron Williams Feb 11 '14 at 18:14
    
I don't know how I did that. It's fixed now. –  Cameron Williams Feb 11 '14 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.