Given a positive integer , we say two sets and of integers are congruent modulo if and only if the residues of elements of modulo are the same as the residues of elements of modulo , and we write . For example,
We say that two sets and of integers are translatable modulo if there is a polynomial with integer coefficients such that either or . Here, by for a subset of integers we mean: .
Find all positive integers such that every two non-empty subsets of are translatable modulo .
Solution
We shall prove that this can only happen whenever is prime. We shall prove the following lemma;
Lemma 1. Let be a prime number and be pair-wise distinct (mod ) and be distinct positive integers. Then, there is a polynomial with integer coefficients such that
Proof. Adopting the Lagrange Interpolation Formula and constructing the following polynomial
where , where by fractions, we mean the multiplicative inverses modulo . It is clear that this polynomial satisfies the condition of the lemma. This completes our proof.
Notice also that if is an arbitrary integer and the preceding lemma remains true. Hence, if and are two arbitrary sets with pair-wise distinct elements mod such that , using the above lemma, we find that would be translatable to .
Let be a composite number and be its smallest prime divisor, it follows that . Now, consider and . We prove that would not be translatable to . On contrary, we shall have , for some . On the other hand, hence, , contradiction. ■