# New to proofs - need a check

1. Oct 4, 2013

### zoxee

Let q be a natural number, show that if q is not divisible by 3, then neither is q^2

proof:

if q is not divisible by 3 then q = 3k + 2 for some integer k
q^2 = 4 + 3(3k^2 + 4k) = 4 + 3m for some integer m, hence q is not divisible by 3

another case, if q = 3k + 1 for some integer k, then q^2 = 1 + 3(3k^2+2k) = 1 + 3n for some integer n, hence q^2 is not divisible by 3

second part:

Assuming the statement that was to be proved above, deduce that there is no rational number x satisfying x^2 = 3

proof:

assume there is some ration number x satisfying x^2 = 3

we can then express x = p/q where p,q are coprime

x^2 = p^2/q^2 = 3
hence p^2 = 3q^2 hence p = 3m for some integer m, i.e. p is divisible by 3 ***(we proved this in the first part)***

therefore 9m^2 = 3q^2 => q^2 = 3m^2 hence q = 3n for some integer n, hence q is also divisible by 3

this is a condradiction as we assumed p and q were coprime, but have shown they have a factor of 3, hence there does not exist a rational number x such that x^2 = 3

ok, is this proof OK? the part I have labelled *** ("***(we proved this in the first part)***") is it true that we proved this in the first part, as we proved that if a natural number is not divisible by 3, then neither is it's square, but in this proof, I am saying if it's square is divisible by 3, then the number is divisible by 3 - is this the same thing (I think it is)

2. Oct 4, 2013

### Office_Shredder

Staff Emeritus
The proof looks fine.... as a formatting thing instead of adding at the end of a line (we proved this in the first part), I would put at the start of the line "by part one,". For example

"hence p^2 = 3q^2 hence p = 3m for some integer m" becomes
"hence p^2 = 3q^2, so by part one p=3m for some integer m"

3. Oct 4, 2013

### zoxee

thanks, so proving that q is not divisible by 3 then neither is q^2 is the same thing as proving if q^2 = 3m (i.e. divisible by 3) then so is q?

4. Oct 4, 2013

### Office_Shredder

Staff Emeritus
Yes, that's called the contrapositive and is often useful. If you have two statements , A and B, then proving if A then B is the same as proving if not B, then not A.

In your case you have A is "q is not divisible by 3", and B is "q2 is not divisible by 3". You proved if A, then B, so you get for free if not B, then not A.

not B is (after cancelling a double negative)"q2 is divisible by 3" and not A is "q is divisible by 3"