# Homework Help: Prove that if 3|2a, then 3|a

1. Feb 28, 2012

### Benn

1. The problem statement, all variables and given/known data

Prove that if 3|2a, then 3|a.

2. Relevant equations

3. The attempt at a solution
I'm pretty sure that I proved it. Although, I feel like something is wrong. Can you check it?

Proof: Assume 3|a, so, by definition, 2a=3q for some q in the integers. And assume 3|a, then a=3p for some p in the integers. Subtracting the second equation from the first equation, we get 2a-a=3q-3p. Simplifying, we get a = 3(q-p). Since q-p is an integer, then 3|a.
QED

As a side note, i chose to assume the consequent because its kind of like when u have the equation x+2=0 and u plug in -2 to see what the answer is..because tehres only 2 options at that point, either x=-2 or x=/=-2 and x=/=-2 shows for an infinite poissbilities of points to check to show a contradiction so I chose instead to assume the one point and show its true.

Last edited: Feb 28, 2012
2. Feb 28, 2012

### Dick

If you assume the consequent then you are assuming the theorem is true before you've even proved it. That's really a bad idea. You need to know something about prime numbers to prove this.

3. Feb 28, 2012

### 1MileCrash

You can assume that the hypothesis is true, and show that the conclusion follows.
You can assume that the negation of the conclusion is true, and that the negation of the hypothesis follows.
You can assume that the hypothesis is true and assume that the conclusion is false, and show that this leads to some type of contradiction.

You can NEVER assume your conclusion is true.

4. Feb 28, 2012

### Benn

but in the context of this problem there are only 2 possibilities, either 3 divides a or 3 does not divide a. is it a well known fact that if 3 does not divide a then 3 does not divide 2a (the contrapositive of the statement) and so is that not all that is necessary to assume the consequent?

5. Feb 28, 2012

### Dick

That "well known fact" is a property of prime numbers. If p is prime and p divides ab, then it divides a or b. 3 is prime. That's what you need to prove this.

6. Feb 28, 2012

### 1MileCrash

7. Feb 29, 2012

### Deveno

to amplify what Dick said:

suppose we factored 2a into primes:

2a = (p1k1)(p2k2)...(prkr).

such a factorization is unique, so if 3 divides 2a, 3 must be one of the primes on the right. is it possible that 3 is one of the powers of 2? i think not. what do we have left when we remove one factor of 2 from the product of prime factors on the right?

8. Feb 29, 2012

### HallsofIvy

Your basic concept is wrong. If the 'theorem' is "if x+ 2= 0 then x= -2", putting x= -2 and showing it satisfies the equation does NOT prove the theorem. Consider the 'theorem', "if $x^2- 3x+ 2= 0$ then x= 2". Setting x= 2 in the equation gives $4- 6+ 2= 0$ all right, but the 'theorem' is false.

9. Feb 29, 2012

### Benn

I know that it's a fundamentally wrong method of proof in a general sense. For example, in your example there are actually 2 options for the solution. In x+2=0 there is guaranteed to be one solution. Its like you have a simple puzzle with one piece missing and you put the missing piece in to see if its right. So you exclude all the other possibilities by just plugging it in and verifying. I understand though that this might not work for other cases where there are multiple options to worry about. So is it then still wrong to prove it that way?

10. Feb 29, 2012

### Dick

Yes, change the problem to: Prove that if 6|2a, then 6|a. You can certainly check that the premise is true if 6|a. But the theorem fails for a=3.

11. Feb 29, 2012

### checkitagain

Don't assume that. You might have a duplicate/indistinguishable
jigsaw piece already placed in the puzzle that you could interchange
with the remaining piece, which would mean that there is not a
unique piece to complete the puzzle.

12. Feb 29, 2012

### intwo

You could try the contrapositive and apply the division algorithm. :)

13. Feb 29, 2012

### Deveno

the point of this problem is that 3 is PRIME. where are the factors of 3 in 2a, are they in the "a" part, or the "2" part?

is it even possible to put "half a factor of 3" somewhere in the "2 part", and the "other half" in the "a part"?

if not, then why not? part of what is means to be prime is: we can't split them up by division.

note how 6|2a --> 6|a goes wrong:

a might be 3, and we can "split 6" into 6 = 2*3, the 2 goes into the "2 part" and the 3 goes into the "a part" (which is all a is, when a = 3).

but when we try to divide 6 into 3, it doesn't work...there's no place to put the factor of 2.

it's good to know how to use the formal definition of "divides" that is, understanding that k|m means that there is some integer d with m = kd. but there's nothing "mysterious" going on here....it should be obvious that 3 just does NOT divide into 2 AT ALL.

14. Feb 29, 2012

### 2e4L

Euclid's lemma: If p is a prime and divides ab (p|ab), then p|a or p|b

15. Feb 29, 2012

### 1MileCrash

Yes! It is always invalid the moment you assume the consequent. Don't you see why? If you assume the consequent, your entire proof is based on the truth of the consequent, how could you arrive at anything other than the consequent being true? It's circular logic.

For example:

Theorem: If the 2 < 5, then elephants are reptiles.

Assume elephants are reptiles.
Then elephants must possess all of the traits of a reptile.
Therefore elephants are reptiles.

Therefore if 2 < 5, then elephants are reptiles.

QED

Plugging in an example to show it works doesn't prove anything for a for all statement. You could negate the statement, which becomes a "there exists" and then plug something into THAT to show that the negation is true, and therefore the theorem is false. That's called a counter example, but that's not what you're doing.

You brought up "if x + 2 = 0, then x = -2." You seem to be under the impression that plugging in -2 is OK because "x + 2 = 0" is "guaranteed" to have only one solution.

However, you have NOT proved that it has only one solution! You just took that it only has one solution as axiom because you know algebra, but that's what you're trying to prove! Of course if x + 2 = 0 only has one solution, and it's -2, then the proposition is true; all you've done by saying that it is "guaranteed to have one solution" is reworded the proposition and assumed that your rewording was true. But you've done nothing to prove that it only has one solution by plugging in -2.

"If x + 2 = 0, then x = - 2."
"Assume x + 2 = 0"
"Then x + 2 - 2 = 0 - 2"
"Therefore x = -2"

Is a valid proof. I have shown that it only has one solution, and that it is -2.

"If x + 2 = 0, then x = - 2."
"Assume x = -2"
"*whatever I want*"
"Then x = -2"

Could never, ever be a proof of anything, other than proof of my inability to do proofs.

Last edited: Feb 29, 2012