6 Mar
2003
6 Mar
'03
12:46 p.m.
Let p be a finite sequence of positive integers, WLOG nondecreasing. Call p "good" (for lack of a better term), if for each p(i) there exists 0 < q(i) < p(i) such that for every integer n, n == q(i) (mod p(i)) for some i. For example, let p = (3, 3, 6, 6), and let q = (0, 1, 2, 5). Since every integer n is of the form 0 (mod 3), 1 (mod 3), 2 (mod 6) or 5 (mod 6), p is good. Clearly, for p to be good, it is necessary that SUM 1/p(i) >= 1, but this is not sufficient. Is there an efficient method to tell if a given p is good?