Problem:
Let be an infinite subset of the set of natural numbers. Determine all natural numbers such that for every it holds that
Problem:
Let be an infinite subset of the set of natural numbers. Determine all natural numbers such that for every it holds that
Denote and ; let , where and are polynomials with integer coefficients and . By the condition of the problem , and hence , for infinitely many integers . Since for sufficiently large we have , it must be that ; therefore, has infinitely many zeros, so and .
Lemma. Let . The polynomial divides if and only if is a complete system of residues modulo .
Proof. Let be the remainder when is divided by . Since divides for all , it follows that divides , where and moreover . If , then , i.e. for some constant , and this holds if and only if and .
From the lemma it follows that the required numbers are those for which is a complete system of residues modulo .
If and is a composite number, then , so the condition is not satisfied. If is prime, by Wilson's theorem , from which , and again the condition is not satisfied. The remaining cases are ; direct verification shows that and satisfy the conditions.
Second solution. We will prove a stronger statement: if divides for some , then is a complete system of residues modulo .
Let . Denote by the remainder when is divided by , and consider the numbers . Then , from which it follows that for . On the other hand, , so since , it must be that for all . From the inequality we conclude that, for every , at most one of the remainders is equal to . But if , then , which is impossible. Therefore, are pairwise distinct modulo , which was to be proved.
From the lemma it follows that the required numbers are those for which is a complete system of residues modulo .
If and is a composite number, then , so the condition is not satisfied. If is prime, by Wilson's theorem , from which , and again the condition is not satisfied. The remaining cases are ; direct verification shows that and satisfy the conditions.