Proving ab ≡ 0 (mod m) and Implications for Divisibility

[imagination10]

ab ≡ 0 (mod m), where a and b are positive integer < m.
Does it follow that either a| m or b| m?


Can anyone give a proof for this ?

 

[0rthodontist]

It isn't true. Try some examples.

 

[Data]

If you know that a and b are prime then it is true. Are you sure the question doesn't specify that?

 

[imagination10]

Hi Orthodontist,

It also can be true.

If a = 2 , b=3 , and m = 6
so 2*3≡ 0 mod 6
so 2|6 , 3|6

Hi Data,
Yes the question does not specify that a and b must be prime.

It is only give a clue that it is related to Zero divisors concept.

 

[HallsofIvy]

imagination10, perhaps it would help if you actually stated the problem. You originally said

"ab ≡ 0 (mod m), where a and b are positive integer < m.
Does it follow that either a| m or b| m?
Can anyone give a proof for this ?"
The answer, as given in the very first response is "no, no one can give a proof because it does not follow."

Your response to Orthodontist, that it can be true is irrelevant. You original question was "is it always true?" The answer to that is "No". Oh, and did you notice that the a and b in your example are prime numbers?

 

[Data]

Maybe it'd help you if you saw a counterexample. Try a=6, b=10, m=15.

 

[StatusX]

This is a little confusing. Saying ab=0 (mod m) is equivalent to saying m|ab. Now, how could it follow in general that a|m or b|m? a and b can be arbitrarily large!

Maybe you mean to ask one of the following: 1) given m=0 (mod ab) (ie, ab|m), does at least one of the following hold: a|m or b|m? It is trivially true that both hold. Or is it 2) given ab=0 (mod m) (ie, m|ab), does one of the following hold: m|a or m|b? This would be true if m is prime.

 

[Data]

he specified a, b &lt; m. Now, of course, if as I suggested earlier, a and b are both prime, and 0&lt; a, b &lt; m, AND you know ab \equiv 0 (\mbox{mod} m), then both a|m and b|m (and in fact m = ab).

And I should have noticed this before, but you only need a or b prime for the original result to hold here.

 

[StatusX]

Ok, I missed that. I thought this was just the classic p|ab=>p|a or p|b problem, but it's actually a little more involved.

So we know that if a,b<m, and m|ab, then km=ab, where k<a,b. As Data says, if a,b are both prime, m=ab. Now assume a is prime and b is composite. Since a|mk and k<a, a|m. Now, if b has any prime divisors p with p<a, we can pick m=ab/p, k=p, and b does not divide m. If, however, b has no prime divisors smaller than a, we must have k=1, m=ab, and so b|m.

Now let's assume both a and b are composite. Assume a<=b, and let p and q be the smallest prime factors of a and b respectively. Now if a<q, k cannot contain any factors of b, and so we must have b|m.

I'm not sure exactly what you're trying to do. If it is just answer the question "Is this true for all a,b,m satisfying these conditions?", then the answer is no, and it shouldn't be hard to constuct a counterexample. If it is to characterize the a,b for which the statement is true, then you can keep going where I left off.