uniolympiads Ελληνικά

IMC 2010, Day 1, Problem 4

Let a,ba, b be two integers and suppose that nn is a positive integer for which the set

Z∖{axn+byn∣x,y∈Z}\mathbb{Z} \setminus \big\{ax^n + by^n \mid x, y \in \mathbb{Z}\big\}

is finite. Prove that n=1n = 1.

Original from the official PDFLet a, b be two integers and suppose that n is a positive integer for which the set Z \ ax n + by n | x, y ∈ Z is finite. Prove that n = 1.

This transcription was compared symbol by symbol with the original, but not yet by a person.

Time on this problem 0:00

Work for at least 45 minutes before opening the solution.

Official solution

Solution. Assume that n>1n>1. Notice that nn may be replaced by any prime divisor pp of nn. Moreover, aa and bb should be coprime, otherwise the numbers not divisible by the greatest common divisor of a,ba,b cannot be represented as axn+bynax^n+by^n.

If p=2p=2, then the number of the form ax2+by2ax^2+by^2 takes not all possible remainders modulo 8. If, say, bb is even, then ax2ax^2 takes at most three different remainders modulo 8, by2by^2 takes at most two, hence ax2+by2ax^2+by^2 takes at most 3×2=63\times2=6 different remainders. If both aa and bb are odd, then ax2+by2≡x2±y2(mod4)ax^2+by^2\equiv x^2\pm y^2 \pmod 4; the expression x2+y2x^2+y^2 does not take the remainder 3 modulo 4 and x2−y2x^2-y^2 does not take the remainder 2 modulo 4.

Consider the case when p≥3p\ge3. The ppth powers take exactly pp different remainders modulo p2p^2. Indeed, (x+kp)p(x+kp)^p and xpx^p have the same remainder modulo p2p^2, and all numbers 0p0^p, 1p1^p, …\dots, (p−1)p(p-1)^p are different even modulo pp. So, axp+bypax^p+by^p take at most p2p^2 different remainders modulo p2p^2. If it takes strictly less then p2p^2 different remainders modulo p2p^2, we get infinitely many non-representable numbers. If it takes exactly p2p^2 remainders, then axp+bypax^p+by^p is divisible by p2p^2 only if both xx and yy are divisible by pp. Hence if axp+bypax^p+by^p is divisible by p2p^2, it is also divisible by ppp^p. Again we get infinitely many non-representable numbers, for example the numbers congruent to p2p^2 modulo p3p^3 are non-representable.

Transcribed from the official solutions, page 3. This transcription has not been checked a second time; if in doubt, look at the original.

Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.

How did it go?