Results 1 to 7 of 7

Math Help - Zero Divisor Problem?

  1. #1
    Banned
    Joined
    Apr 2009
    Posts
    96

    Zero Divisor Problem?

    I posted a thread about modular math but this has a different application.

    Suppose that a*b = 0 (mod n), and that a and b are positive integers both less than n.

    Does it follow that either a|n or b|n? If so, why? If not, is there an example providing the contrary?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    Quote Originally Posted by 1337h4x View Post
    I posted a thread about modular math but this has a different application.

    Suppose that a*b = 0 (mod n), and that a and b are positive integers both less than n.

    Does it follow that either a|n or b|n? If so, why? If not, is there an example providing the contrary?
    There are many easy counter-examples. Did you try anything?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Banned
    Joined
    Apr 2009
    Posts
    96
    Quote Originally Posted by Bruno J. View Post
    There are many easy counter-examples. Did you try anything?
    Yes, but as I said, modular math is relatively new to me. I'm asking these questions so I get a better understanding of how this works.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Mar 2010
    Posts
    993
    Thanks
    244
    The notation ab\equiv{0}\ (\text{mod }n) means that ab is divisible by n, or n | ab, which means there is an integer m such that ab=mn. But you can't conclude that a | n or b | n, since some of the prime factors of a and b might be contained in m.

    As Bruno J. said, it's easy to find counter examples. Here's one:
    a=6, b=5, m=10, n=3: ab=30, so ab\equiv{0}\ (\text{mod }3) and neither 6 nor 5 divides 3.

    - Hollywood
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Banned
    Joined
    Apr 2009
    Posts
    96
    Thanks!!!!! That makes sense!
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by 1337h4x View Post
    I posted a thread about modular math but this has a different application.

    Suppose that a*b = 0 (mod n), and that a and b are positive integers both less than n.

    Does it follow that either a|n or b|n? If so, why? If not, is there an example providing the contrary?
    Quote Originally Posted by hollywood View Post
    As Bruno J. said, it's easy to find counter examples. Here's one:
    a=6, b=5, m=10, n=3: ab=30, so ab\equiv{0}\ (\text{mod }3) and neither 6 nor 5 divides 3.
    That example doesn't quite work, because the condition in red is not satisfied: 6 and 5 are not less than 3. What you need is that a and b between them contain all the factors of n, but neither a nor b individually contains all the factors of n. In addition, a and b must each have some factor that is not a factor of n. For example, a=6, b=10, n=15.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member
    Joined
    Mar 2010
    Posts
    993
    Thanks
    244
    Quote Originally Posted by Opalg View Post
    That example doesn't quite work, because the condition in red is not satisfied: 6 and 5 are not less than 3. What you need is that a and b between them contain all the factors of n, but neither a nor b individually contains all the factors of n. In addition, a and b must each have some factor that is not a factor of n. For example, a=6, b=10, n=15.
    Good point! Thanks.

    - Hollywood
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. divisor problem
    Posted in the Algebra Forum
    Replies: 1
    Last Post: April 29th 2010, 08:20 AM
  2. Dirichlet Divisor problem
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: August 7th 2009, 02:12 PM
  3. divisor
    Posted in the Advanced Algebra Forum
    Replies: 5
    Last Post: April 17th 2009, 05:43 AM
  4. Greatest Common Divisor Word Problem
    Posted in the Algebra Forum
    Replies: 1
    Last Post: November 25th 2008, 11:09 PM
  5. An extension of Dirichlet's Divisor Problem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 5th 2008, 06:26 AM

Search Tags


/mathhelpforum @mathhelpforum