The quadratic equation x^2-3x+2=0 has the "correct" number of solutions modulo 5 and 7. However, modulo 6 the equation has four solutions; namely, 1, 2, 4, and 5. For what positive integers n does the equation x^2-3x+2=0 have exactly two incongruent solutions modulo n?

x^2-3x+2 factors into (x-2)(x-1) no matter what modulo it's in.  Therefore, 2 and 1 are solutions for all moduli.  However, in modular arithmetic, the zero product property is not always true.  That is, if xy=0, it is possible for neither x nor y to be zero.

Since we are considering integers, the zero product property is true for all prime n.  Therefore, the set of all primes is a subset of the looked-for set.

If n is a non-prime, it does not necessarily mean that there are more than two solutions modulo n.  The question is, "Can the product of two nonzero consecutive integers be zero?"  Not for all composite n, n=4 being a counterexample.

What n do work?  That's relatively easy: For any positive integer k, all the positive divisors of k*(k+1), minus the divisors of k and k+1, work.  But we need a simpler way of describing this set.

k and k+1 are, of course, relatively prime.  The associated values of n need to include at least one factor from k and one from k+1.  For this reason, integral powers of primes are not possible values for n.  All other values of n work because if n has at least two distinct prime factors, then it can be written as the product of two relatively prime numbers greater than 0, and as we all know, for any relatively prime a and b, there exist an x and y for which ax-by=1.

So the set we are looking for is the set of all primes and their integral powers.  This is confirmed by Charlie's wonderful program.

I look forward to seeing proofs simpler than mine.

Posted by Tristan on 2005-09-03 20:55:03