Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: How to prove this?

  1. Aug 2, 2006 #1
    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 ?
  2. jcsd
  3. Aug 2, 2006 #2


    User Avatar
    Science Advisor

    It isn't true. Try some examples.
  4. Aug 2, 2006 #3
    If you know that [itex]a[/itex] and [itex]b[/itex] are prime then it is true. Are you sure the question doesn't specify that?
    Last edited: Aug 2, 2006
  5. Aug 3, 2006 #4
    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.
  6. Aug 3, 2006 #5


    User Avatar
    Science Advisor

    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?
  7. Aug 3, 2006 #6
    Maybe it'd help you if you saw a counterexample. Try a=6, b=10, m=15.
  8. Aug 3, 2006 #7


    User Avatar
    Homework Helper

    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.
  9. Aug 3, 2006 #8
    he specified [itex]a, b < m.[/itex] Now, of course, if as I suggested earlier, a and b are both prime, and [itex]0< a, b < m[/itex], AND you know [itex]ab \equiv 0 (\mbox{mod} m)[/itex], then both a|m and b|m (and in fact m = ab).

    And I should have noticed this before, but you only need [itex]a[/itex] or [itex]b[/itex] prime for the original result to hold here.
    Last edited: Aug 3, 2006
  10. Aug 3, 2006 #9


    User Avatar
    Homework Helper

    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.
    Last edited: Aug 3, 2006
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook