Maths Olympiad Prep

Library / /86 of 92

Number theory Difficulty 7.5 National olympiad, round 2 Prove it Iran

Let a,a1,...,ana, a_1, ..., a_n be positive integers. We know that for any positive integer kk where ak+1ak + 1 is a square number, at least one of the numbers a1k+1,...,ank+1a_1k + 1, ..., a_nk + 1 is also a square. Prove that a{a1,...,an}a \in \{a_1, ..., a_n\}.

Solutions — 2

Solution 1

Lemma. If PP is a polynomial with integer coefficients and a square leading coefficient which for infinitely many numbers nn, P(n)P(n) is a square number, then there exists a QZ[x]Q \in \mathbb{Z}[x] which
P(x)=Q(x)2 P(x) = Q(x)^2
Assume P(x)P(x) has the following representation
P(x)=cnxn+cn1xn1++c0 P(x) = c_n x^n + c_{n-1} x^{n-1} + \dots + c_0
According to the assumptions, there exists an integer number cc which
c2=cn    P(x)=c2xn+cn1xn1++c0 c^2 = c_n \implies P(x) = c^2 x^n + c_{n-1} x^{n-1} + \dots + c_0
Set k=as2+2sk = as^2 + 2s.
ak+1=a(as2+2s)+1=a2s2+2as+1=(as+1)2 ak + 1 = a(as^2 + 2s) + 1 = a^2s^2 + 2as + 1 = (as + 1)^2
Since ak+1ak+1 is a square number by the assumption one of the numbers aik+1a_i k+1 must be a square.
For every integer 1in1 \le i \le n define polynomial Pi(s)P_i(s) by the following equation.
Pi(s)=ai(as2+2s)+1=aais2+2ais+1(1) P_i(s) = a_i(as^2 + 2s) + 1 = aa_i s^2 + 2a_i s + 1 \quad (1)
So Pi(s)P_i(s) is a square for an integer ii. Now put s,s+1,,s+ns, s+1, \dots, s+n in these polynomials. By applying pigeonhole principle two of these ii's are equal so Pi(s+t),Pi(s+k)P_i(s+t), P_i(s+k) are square numbers for some 0t,kn0 \le t, k \le n. If ss goes to infinity, for each ss there is a triple (i,j,k)(i, j, k), which Pi(s+t),Pi(s+k)P_i(s+t), P_i(s+k) are square numbers. Since there are only finite number of these triples so there are infinite numbers ss such that they have same triples.
Define polynomial PP such that
P(s)=Pi(s+t)Pi(s+k). P(s) = P_i(s+t)P_i(s+k).
Since Pi(s+t),Pi(s+k)P_i(s+t), P_i(s+k) are squares so P(s)P(s) is a square number too. Also because Pi(s+t),Pi(s+k)P_i(s+t), P_i(s+k) are polynomials of degree 2 with the same leading coefficient aaiaa_i then P(s)P(s) is a polynomial of degree 4 with a square leading coefficient.
The lemma suggests that there exists a polynomial of degree 2 such that
P(x)=Q(x)2 P(x) = Q(x)^2
also
P(x)=Pi(x+t)Pi(x+k) P(x) = P_i(x+t)P_i(x+k)
by putting together
Pi(x+t)Pi(x+k)=Q(x)2. P_i(x+t)P_i(x+k) = Q(x)^2.
Let D(x)D(x) be the greatest common divisor of Pi(x+t),Pi(x+k)P_i(x+t), P_i(x+k) so
Pi(x+t)=D(x)A(x)2,Pi(x+k)=D(x)B(x)2 P_i(x+t) = D(x)A(x)^2, \quad P_i(x+k) = D(x)B(x)^2
Notice that Pi(x+t),Pi(x+k)P_i(x+t), P_i(x+k) are polynomials of degree 2 so either of A,BA, B are constant or of degree one. If they are constant Pi(x+t),Pi(x+k)P_i(x+t), P_i(x+k) should be a multiple of each other but they have same leading coefficients then they are equal which is a contradiction because we chose different t,kt, k. So DD should be a constant but for infinite integers ss, D(s)A(s)2D(s)A(s)^2 is a square number so for some ss, which A(s)0A(s) \ne 0 because a,aia, a_i are positive integers and then PiP_i can't be zero.
D=d2    Pi(x+t)=(dA(x))2,Pi(x+k)=(dB(x))2    (mx+p)2=Pi(x)=(1)aaix2+2aix+1 \begin{align*} D &= d^2 \implies P_i(x+t) = (dA(x))^2, \quad P_i(x+k) = (dB(x))^2 \\ \implies (mx+p)^2 &= P_i(x) \stackrel{(1)}{=} aa_i x^2 + 2a_i x + 1 \end{align*}
so p2=1p^2 = 1. If p=1p = -1 take
(mxp)2=(mx+p)2 (-mx - p)^2 = (mx + p)^2
so without loss of generality, take p=1p = 1
aaix2+2aix+1=(mx+1)2 aa_i x^2 + 2a_i x + 1 = (mx + 1)^2
by comparing coefficients
aai=m2, 2ai=2m aa_i = m^2, \ 2a_i = 2m
from the last equation ai=ma_i = m so by putting this into the first equation
aai=ai2ai0ai0a=ai aa_i = a_i^2 \underset{a_i \neq 0}{\stackrel{a_i \neq 0}{\Rightarrow}} a = a_i
then
a{a1,a2,,an} a \in \{a_1, a_2, \dots, a_n\}
and we are done.

Solution 2

As the first solution take k=as2+2sk = as^2 + 2s. So for an integer ii, Pi(s)P_i(s) is a square number. i.e.
Pi(s)=ai(as2+2s)+1=aais2+2ais+1 P_i(s) = a_i(as^2 + 2s) + 1 = aa_i s^2 + 2a_i s + 1
is a square.
(ais+1)2=ai2s2+2ais+1 (a_i s + 1)^2 = a_i^2 s^2 + 2a_i s + 1
by subtracting these two equalities
Pi(s)(ais+1)2=(aais2+2ais+1)(ai2s2+2ais+1)=ai(aai)s2impliesPi(s)(ais+1)2=ai(aai)s2(2) \begin{aligned} P_i(s) - (a_i s + 1)^2 &= (aa_i s^2 + 2a_i s + 1) - (a_i^2 s^2 + 2a_i s + 1) = a_i(a - a_i)s^2 \\ implies P_i(s) - (a_i s + 1)^2 &= a_i(a - a_i)s^2 \end{aligned} \qquad (2)
By the assumption there is a positive integer nin_i which
ni2=Pi(s) n_i^2 = P_i(s)
so by putting this in (2)
ai(aai)s2=Pi(s)(ais+1)2=ni2(ais+1)2=(niais1)(ni+ais+1) a_i(a - a_i)s^2 = P_i(s) - (a_i s + 1)^2 = n_i^2 - (a_i s + 1)^2 = (n_i - a_i s - 1)(n_i + a_i s + 1)
Let ss be a prime number. Assume that aaia \neq a_i. By the equality s2s^2 divides the right hand side.
s2(niais1)(ni+ais+1) s^2 \mid (n_i - a_i s - 1)(n_i + a_i s + 1)
If ss divides both of the numbers in the parentheses
sniais1,sni+ais+1 s \mid n_i - a_i s - 1, \quad s \mid n_i + a_i s + 1
By subtracting
s2ais+2    s2 s \mid 2a_i s + 2 \implies s \mid 2
So ss only divides one of these numbers and by assuming aai0a - a_i \neq 0
s2max(niais1,ni+ais+1)ai0ai0s2ni+ais+1 s^2 \leq \max(n_i - a_i s - 1, n_i + a_i s + 1) \underset{a_i \geq 0}{\stackrel{a_i \geq 0}{\Rightarrow}} s^2 \leq n_i + a_i s + 1
Notice that the right hand side is approximately a polynomial of degree one in terms of ss and it's a contradiction
s2ni+ais+1=aais2+2ais+1+ais+1impliess2ais1aais2+2ais+1 \begin{aligned} s^2 &\le n_i + a_i s + 1 = \sqrt{aa_i s^2 + 2a_i s + 1} + a_i s + 1 \\ implies s^2 - a_i s - 1 &\le \sqrt{aa_i s^2 + 2a_i s + 1} \end{aligned}
For large enough prime number ss the left hand side is a positive integer so by taking square of both sides.
(s2ais1)2ais22ais1    (s2ais1)2ais22ais10 (s^2 - a_i s - 1)^2 \le a_i s^2 - 2a_i s - 1 \implies (s^2 - a_i s - 1)^2 - a_i s^2 - 2a_i s - 1 \le 0
This inequality says that a polynomial of degree four with a positive leading coefficient is a negative number for infinite prime numbers which is a contradiction. Notice that there are only nn possibilities for ii so for infinite prime numbers there is an integer ii that these equalities hold. ■

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 and solution reproduced as published; topic and difficulty added by this site.