Proving the Divisibility Property of Prime Numbers: A Simple Guide

[mephillip]

Homework Statement

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.

Homework Equations

pk=a
a=pq+r

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.

 

[FactChecker]

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

 

[Ray Vickson]

Homework Statement

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.

Homework Equations

pk=a
a=pq+r

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.

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

 

[mephillip]

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

What do you mean?

 

[Logical Dog]

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

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.

 

[Ray Vickson]

What do you mean?

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?

 

[FactChecker]

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.

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.

 

[haruspex]

and one of a and b is greater than P?

That is not a necessary additional condition.

 

[Logical Dog]

That is not a necessary additional condition.

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

 

[haruspex]

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

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.

 

[Logical Dog]

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.

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.