Maths Olympiad Prep

Library / /275 of 299

Number theory Difficulty 7.6 National Olympiad, round 2 Prove it Iran

Given a positive integer nn, we say two sets AA and BB of integers are congruent modulo nn if and only if the residues of elements of AA modulo nn are the same as the residues of elements of BB modulo nn, and we write AB(modn)A \equiv B \pmod{n}. For example,
{3,5,8}{4,0,9,15}(mod3) \{3, 5, 8\} \equiv \{-4, 0, 9, 15\} \pmod{3}
We say that two sets AA and BB of integers are translatable modulo nn if there is a polynomial f(x)f(x) with integer coefficients such that either f(A)B(modn)f(A) \equiv B \pmod{n} or f(B)A(modn)f(B) \equiv A \pmod{n}. Here, by f(X)f(X) for a subset XX of integers we mean: f(X)={f(x):xX}f(X) = \{f(x) : x \in X\}.
Find all positive integers n>4n > 4 such that every two non-empty subsets of {0,1,,n1}\{0, 1, \dots, n-1\} are translatable modulo nn.

Solution

We shall prove that this can only happen whenever nn is prime. We shall prove the following lemma;

Lemma 1. Let pp be a prime number and x1,,xrx_1, \cdots, x_r be pair-wise distinct (mod pp) and y1,,yry_1, \cdots, y_r be distinct positive integers. Then, there is a polynomial P(x)P(x) with integer coefficients such that
P(xi)yi(modp) P(x_i) \equiv y_i \pmod{p}
Proof. Adopting the Lagrange Interpolation Formula and constructing the following polynomial
ai(xx1)(xxr)(xxi) \sum a_i \cdot \frac{(x-x_1)\cdots(x-x_r)}{(x-x_i)}
where ai=yi/((xix1)(xixi1)(xixi+1)(xixn))a_i = y_i/((x_i-x_1)\cdots(x_i-x_{i-1})(x_i-x_{i+1})\cdots(x_i-x_n)), where by fractions, we mean the multiplicative inverses modulo pp. It is clear that this polynomial satisfies the condition of the lemma. This completes our proof.

Notice also that if nn is an arbitrary integer and gcd(xixj,n)=1\gcd(x_i - x_j, n) = 1 the preceding lemma remains true. Hence, if AA and BB are two arbitrary sets with pair-wise distinct elements mod pp such that AB|A| \ge |B|, using the above lemma, we find that AA would be translatable to BB.
Let n>4n > 4 be a composite number and pp be its smallest prime divisor, it follows that n>3pn > 3p. Now, consider A={1,p+1,2p+1}A = \{1, p+1, 2p+1\} and B={1,2}B = \{1, 2\}. We prove that BB would not be translatable to AA. On contrary, we shall have P(R)1,P(S)2(modp)P(R) \equiv 1, P(S) \equiv 2 \pmod{p}, for some R,SAR, S \in A. On the other hand, RS(modp)R \equiv S \pmod{p} hence, P(R)P(S)(modp)P(R) \equiv P(S) \pmod{p}, contradiction. ■

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.