congruence proof: Prove that there is no integer such that $x≡2 \pmod 6$ and $x≡3 \pmod 9$ are both true.

Question

Prove that there is no Integer such that $x≡2 \pmod 6$ and $x≡3 \pmod 9$ are both true.

How should I approach this question?
I attempted using contra-positive proof, so $x=6p+2$ and $x=9q+3$ where $p,q$ are integers.
Then $6p+2=9q+3$.

Abhra Abir Kundu · Accepted Answer · 2013-06-17T13:53:47.033

1

$x=6k+2=9l+3$ for some $k,l\in N$ ,

$3$ divides $9l+3\Rightarrow 3|6k+2$

What does $3|(6k+2)$ imply?

Doesn't this imply the impossible fact $3|2$.

So it is a contraction to the given fact.

edited Jun 17 '13 at 13:53

answered Jun 17 '13 at 13:48

Abhra Abir Kundu

thanks! that really helps. – calakala Jun 17 '13 at 13:56
you are welcome.....it was my pleasure helping you. – Abhra Abir Kundu Jun 17 '13 at 13:56

score 1 · Answer 2 · answered Jun 17 '13 at 13:49

1

It can't be true that for integers $k,k'$ we have $6k-9k'=1$ or $3k''=1$ for some integer $k''$.

answered Jun 17 '13 at 13:49

Mikasa

score 1 · Answer 3 · answered Jun 17 '13 at 13:59

You have the right idea and you are doing well. You said you got to $$6p+2=9q+3.$$

You are almost done! Move the $6p$ to the other side:

$$\begin{align}2 & = 9q + 3 - 6p\\ 2 & = 3(q+1-2p)\end{align}$$

There is a multiple of 3 on the right, so it says that 2 is equal to a multiple of 3. Do you have the contradiction you want?

score 1 · Answer 4 · answered Jun 17 '13 at 14:30

1

HINT:

$$x\equiv2\pmod 6\equiv2\pmod 3$$

and $$x\equiv3\pmod 9\equiv0\pmod 3$$

answered Jun 17 '13 at 14:30

lab bhattacharjee

4 Answers4