Thread: 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?

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?

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.

The notation 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 and neither 6 nor 5 divides 3.

- Hollywood

Thanks!!!!! That makes sense!

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

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