How to prove this?

1. Feb 14, 2017

mephillip

1. The problem statement, all variables and given/known data
Prove or disprove: let a and b be integers and let p be a prime number. If p divides ab then p divides a or p divides b.

2. Relevant equations
pk=a
a=pq+r

3. The attempt at a solution
Contrapositive: if p does not divide a and p does not divide b, then p does not divide ab.
p divides a for some integer k; pk=a
p does not divide a for some integer q and r; a=pq+r
If p divides ab and p does not divide a, then p divides b.
gcd(p,a)=1; there exists integers u and v such that pu+av=1.

2. Feb 14, 2017

FactChecker

To prove directly, rather than using contrapositive, apply the unique factorization theorem to factor ab and see where that gets you.

3. Feb 14, 2017

Ray Vickson

What tools/results are you permitted to know/use?

4. Feb 14, 2017

mephillip

What do you mean?

5. Feb 14, 2017

Logical Dog

Hello.sorry if this is wrong....I thought it would only work if a and b are greater than zero and one of a and b is greater than P? I also don't understand the question, sure if a and b are both negative(as it says are in integers) p can divide the product, but not both individually using other factors which are only primes? right? so to use the factorisation of primes, I think a or b > 0, and a or b > P

assuming just using two lists of primes for a and b.

Last edited: Feb 14, 2017
6. Feb 14, 2017

Ray Vickson

I mean exactly what I say. Have you already seen some theorems about integers, primes, etc.? Do you know about prime factorization? So, what material do you have available to work with?

7. Feb 14, 2017

FactChecker

Good point. To give a complete proof, the possibility of negative numbers needs to be considered. I think that can be taken care of by proving it for all positive numbers and handling negative numbers as corollaries.

8. Feb 17, 2017

haruspex

That is not a necessary additional condition.

9. Feb 17, 2017

Logical Dog

Yes, I think I understand. Is it because a= b =p is not ruled out??

10. Feb 17, 2017

haruspex

No, it's because you are given that p divides ab, so (if nonnegative) you can prove that at least one of them is greater than p.

11. Feb 17, 2017

Logical Dog

Oh, I think that is what I meant originally but now I am not sure as I said a or b > p and then one of a and b > p.,
thank you, i must study the basics again.

Last edited: Feb 17, 2017