# Math Help - Zero Divisor Problem?

1. ## 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?

2. Originally Posted by 1337h4x
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?

3. Originally Posted by Bruno J.
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.

4. 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

5. Thanks!!!!! That makes sense!

6. Originally Posted by 1337h4x
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?
Originally Posted by hollywood
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.

7. Originally Posted by Opalg
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