Maths Olympiad Prep

Library / /462 of 520

Number theory Difficulty 7.3 National olympiad, round 2 Prove it

Let SS be a set of integers. We say that SS is beautiful if it contains all integers of the form 2a2b2^{a}-2^{b}, where aa and bb are non-zero natural numbers. We also say that SS is strong if, for any non-constant polynomial P(X)P(X) with coefficients in SS, the integer roots of P(X)P(X) also belong to SS.
Find all sets that are both beautiful and strong.

Solution

The set Z\mathbb{Z} is clearly beautiful and strong. We will prove that it is the only one. To do this, consider a set SS that is beautiful and strong: we will actually prove, by strong induction on nn, that the integers nn and n-n necessarily belong to SS.
First, since SS is beautiful, it contains the integers 2121=0,2221=22^{1}-2^{1}=0, 2^{2}-2^{1}=2, and 2122=22^{1}-2^{2}=-2. It also contains the integers 1 and -1, which are roots of the polynomials 22X2-2X and 2+2X2+2X, respectively.
We now consider an integer n3n \geqslant 3 such that n1,,n1-n-1, \ldots, n-1 all belong to SS. Let α\alpha be the 2-adic valuation of nn, and mm be the odd integer such that n=2αmn=2^{\alpha} m. By noting φ(m)\varphi(m) as the Euler's totient function of mm, we observe that the integer k=2α+φ(m)+12α+1k=2^{\alpha+\varphi(m)+1}-2^{\alpha+1}, which clearly belongs to SS, is also a multiple of 2α2^{\alpha} and mm, and thus of nn.
Let aa1a0\overline{a_{\ell} a_{\ell-1} \ldots a_{0}} be the base-nn representation of k/nk / n. All the integers ±a0,,±a\pm a_{0}, \ldots, \pm a_{\ell} are between 1n1-n and n1n-1, and thus belong to SS. By construction, nn is an integer root of the polynomial P(X)=ki=0aiXi+1P(X)=k-\sum_{i=0}^{\ell} a_{i} X^{i+1}, whose coefficients are all in SS, so nn is in SS as well. Similarly, n-n is an integer root of the polynomial Q(X)=ki=0ai(X)i+1Q(X)=k-\sum_{i=0}^{\ell} a_{i}(-X)^{i+1}, so nS-n \in S, which concludes the induction and the proof.

Remark: Given the statement, one could suspect that using polynomials of degree d2d \geqslant 2 might be useful, otherwise the creators of the statement would have directly chosen to define strong sets as sets stable under division. The remark below is mainly intended to illustrate the fact that if one seeks to drastically simplify a hypothesis in a mathematical statement, here with the goal of showing that Z\mathbb{Z} would be the only beautiful set stable under division, it is very important to look for simple constructions that could invalidate this simplification.
We will in fact prove that there exists a set SS that is beautiful and stable under division, but different from Z\mathbb{Z}: this demonstrates that using polynomials of degree d2d \geqslant 2 was actually necessary to solve this problem. To construct this set, we need Zsygmondy's theorem and the known property that there exist Fermat numbers (i.e., integers of the form 2p12^{p}-1) that are not prime, even if pp is large enough (below, we will need the inequality p7p \geqslant 7). For example, when p=11p=11, 2111=23×892^{11}-1=23 \times 89. Indeed, write 2p12^{p}-1 as the product 2p1=q×r×m2^{p}-1=q \times r \times m, where qq and rr are two primes, and mm is any integer. We then consider the set SS consisting of 0 and integers of the form

±2ak2(2k1)αk \pm 2^{a} \prod_{k \geqslant 2}\left(2^{k}-1\right)^{\alpha_{k}}

where the αk\alpha_{k} are integers, only finitely many of which are non-zero. The set SS is clearly beautiful and stable under division.
Suppose now that qSq \in S: we then write qq as

q=k2(2k1)αk q=\prod_{k \geqslant 2}\left(2^{k}-1\right)^{\alpha_{k}}

and let \ell be the maximal index such that α0\alpha_{\ell} \neq 0. Since the order of 2 modulo qq and rr divides pp, it is equal to pp, so p7\ell \geqslant p \geqslant 7.

Zsygmondy's theorem then indicates that there exists a prime ss that divides 212^{\ell}-1 and no integer 2k12^{k}-1 for 1k11 \leqslant k \leqslant \ell-1. We then note that

vs(q)=k2αkvs(2k1)=αvs(21)0. v_{s}(q)=\sum_{k \geqslant 2} \alpha_{k} v_{s}\left(2^{k}-1\right)=\alpha_{\ell} v_{s}\left(2^{\ell}-1\right) \neq 0 .

We deduce that s=qs=q, so =p\ell=p, and that vq(21)=1v_{q}\left(2^{\ell}-1\right)=1. This means in particular that rqr \neq q. But then, even for =p\ell=p, and instead of choosing s=qs=q, we could have satisfied Zsygmondy's theorem by choosing s=rs=r, leading to a contradiction. We therefore conclude that qSq \notin S, and thus that SZS \neq \mathbb{Z}.

Comment from the graders: This number theory problem was quite difficult as it required a trick: the simplest solution involved the base-bb decomposition of an integer. Only five students thought of this and they all received the maximum score. The grading scale valued this trick, making it impossible to score more than 3 if this base decomposition was not mentioned.
Almost all students realized that the only beautiful and strong set would be Z\mathbb{Z}, without necessarily knowing how to prove it.
Many students tried to show that every integer (sometimes restricted to odd or prime integers) had a multiple in SS, which was essential for the subsequent steps. Many also showed that SS was symmetric with respect to 0 (i.e., if nSn \in S, then nS-n \in S), which allows avoiding dealing with negative integers in the subsequent steps.
Let's finally address some common errors:
\triangleright Managing negative integers sometimes led to a significant error, especially when students attempted to prove by induction that 1,nS\llbracket 1, n \rrbracket \subseteq S for all n1n \geqslant 1. Some students introduced an integer k1k \geqslant 1 such that nkSn k \in S, and they claimed that nkn-k belonged to SS by induction hypothesis as an integer strictly less than nn. However, these students did not rule out the case where k2nk \geqslant 2 n, so it was possible to have nknn-k \leqslant -n, thus undermining their entire reasoning.
\triangleright Some students noted that it sufficed for all primes to be in SS to conclude. This is true, but no known solution immediately proves this result. In this case, several students thought they had solved the problem by showing this result. They based their reasoning on the belief (erroneous, as indicated in the remark above) that if nn and mm are two distinct odd natural numbers, then the order of 2 modulo nn is different from the order of 2 modulo mm. This error is equivalent to the misconception of Zsigmondy's theorem, which states that for n{1,6}n \notin\{1,6\}, 2n12^{n}-1 has exactly one primitive prime divisor.
\triangleright Finally, vague arguments like "we construct more and more integers by taking the integer roots of polynomials with coefficients in an increasingly large set" can help form an idea, but obviously do not earn any points.
It is worth noting that in a problem like this, explicitly verifying that small values of nn (e.g., n=0,n=1n=0, n=1, and n=2n=2) are in SS always earns a point, yet some students did not have this reflex.
Finally, many students proved that if abSa b \in S and aSa \in S is non-zero, then bSb \in S. This result, while correct, is misleading because it invites the use of only the degree 1 polynomials in the statement, which are clearly insufficient to conclude, as indicated in the remark above.
! if the equality

f(f(x+y)+y)=f(f(x)+y) f(f(x+y)+y)=f(f(x)+y)

is satisfied for all integers xx and yy. An integer vv is said to be ff-rare if the set of integers xx such that f(x)=vf(x)=v is a finite and non-empty set.
a) Prove that there exists a Russian function ff for which there exists an ff-rare integer.
b) Prove that for any Russian function ff, there is at most one ff-rare integer.

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.