Let be a set of integers. We say that is beautiful if it contains all integers of the form , where and are non-zero natural numbers. We also say that is strong if, for any non-constant polynomial with coefficients in , the integer roots of also belong to .
Find all sets that are both beautiful and strong.
Solution
The set is clearly beautiful and strong. We will prove that it is the only one. To do this, consider a set that is beautiful and strong: we will actually prove, by strong induction on , that the integers and necessarily belong to .
First, since is beautiful, it contains the integers , and . It also contains the integers 1 and -1, which are roots of the polynomials and , respectively.
We now consider an integer such that all belong to . Let be the 2-adic valuation of , and be the odd integer such that . By noting as the Euler's totient function of , we observe that the integer , which clearly belongs to , is also a multiple of and , and thus of .
Let be the base- representation of . All the integers are between and , and thus belong to . By construction, is an integer root of the polynomial , whose coefficients are all in , so is in as well. Similarly, is an integer root of the polynomial , so , which concludes the induction and the proof.
Remark: Given the statement, one could suspect that using polynomials of degree 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 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 that is beautiful and stable under division, but different from : this demonstrates that using polynomials of degree 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 ) that are not prime, even if is large enough (below, we will need the inequality ). For example, when , . Indeed, write as the product , where and are two primes, and is any integer. We then consider the set consisting of 0 and integers of the form
where the are integers, only finitely many of which are non-zero. The set is clearly beautiful and stable under division.
Suppose now that : we then write as
and let be the maximal index such that . Since the order of 2 modulo and divides , it is equal to , so .
Zsygmondy's theorem then indicates that there exists a prime that divides and no integer for . We then note that
We deduce that , so , and that . This means in particular that . But then, even for , and instead of choosing , we could have satisfied Zsygmondy's theorem by choosing , leading to a contradiction. We therefore conclude that , and thus that .
Comment from the graders: This number theory problem was quite difficult as it required a trick: the simplest solution involved the base- 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 , 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 , which was essential for the subsequent steps. Many also showed that was symmetric with respect to 0 (i.e., if , then ), which allows avoiding dealing with negative integers in the subsequent steps.
Let's finally address some common errors:
Managing negative integers sometimes led to a significant error, especially when students attempted to prove by induction that for all . Some students introduced an integer such that , and they claimed that belonged to by induction hypothesis as an integer strictly less than . However, these students did not rule out the case where , so it was possible to have , thus undermining their entire reasoning.
Some students noted that it sufficed for all primes to be in 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 and are two distinct odd natural numbers, then the order of 2 modulo is different from the order of 2 modulo . This error is equivalent to the misconception of Zsigmondy's theorem, which states that for , has exactly one primitive prime divisor.
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 (e.g., , and ) are in always earns a point, yet some students did not have this reflex.
Finally, many students proved that if and is non-zero, then . 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
is satisfied for all integers and . An integer is said to be -rare if the set of integers such that is a finite and non-empty set.
a) Prove that there exists a Russian function for which there exists an -rare integer.
b) Prove that for any Russian function , there is at most one -rare integer.