Maths Olympiad Prep

Library / /6 of 16

Number theory Difficulty 8.4 Shortlist Prove it IMO

Let aa and bb be distinct integers greater than 11. Prove that there exists a positive integer nn such that (an1)(bn1)(a^{n}-1)(b^{n}-1) is not a perfect square.

Solutions — 2

Solution 1

At first we notice that
(1α)12(1β)12=(112α18α2)(112β18β2)=k,0ck,αkβ for all α,β(0,1) \begin{align*} (1-\alpha)^{\frac{1}{2}}(1-\beta)^{\frac{1}{2}} & =\left(1-\frac{1}{2} \cdot \alpha-\frac{1}{8} \cdot \alpha^{2}-\cdots\right)\left(1-\frac{1}{2} \cdot \beta-\frac{1}{8} \cdot \beta^{2}-\cdots\right) \\ & =\sum_{k, \ell \geq 0} c_{k, \ell} \cdot \alpha^{k} \beta^{\ell} \quad \text{ for all } \alpha, \beta \in(0,1) \end{align*}
where c0,0=1c_{0,0}=1 and ck,c_{k, \ell} are certain coefficients.
For an indirect proof, we suppose that xn=(an1)(bn1)Zx_{n}=\sqrt{(a^{n}-1)(b^{n}-1)} \in \mathbb{Z} for all positive integers nn. Replacing aa by a2a^{2} and bb by b2b^{2} if necessary, we may assume that aa and bb are perfect squares, hence ab\sqrt{a b} is an integer.
At first we shall assume that aμbνa^{\mu} \neq b^{\nu} for all positive integers μ,ν\mu, \nu. We have
xn=(ab)n(11an)12(11bn)12=k,0ck,(abakb)n. \begin{equation*} x_{n}=(\sqrt{a b})^{n}\left(1-\frac{1}{a^{n}}\right)^{\frac{1}{2}}\left(1-\frac{1}{b^{n}}\right)^{\frac{1}{2}}=\sum_{k, \ell \geq 0} c_{k, \ell}\left(\frac{\sqrt{a b}}{a^{k} b^{\ell}}\right)^{n} . \end{equation*}
Choosing k0k_{0} and 0\ell_{0} such that ak0>ab,b0>aba^{k_{0}}>\sqrt{a b}, b^{\ell_{0}}>\sqrt{a b}, we define the polynomial
P(x)=k=0,=0k01,01(akbxab)=:i=0k00dixi P(x)=\prod_{k=0, \ell=0}^{k_{0}-1, \ell_{0}-1}\left(a^{k} b^{\ell} x-\sqrt{a b}\right)=: \sum_{i=0}^{k_{0} \cdot \ell_{0}} d_{i} x^{i}
with integer coefficients did_{i}. By our assumption, the zeros
abakb,k=0,,k01,=0,,01, \frac{\sqrt{a b}}{a^{k} b^{\ell}}, \quad k=0, \ldots, k_{0}-1, \quad \ell=0, \ldots, \ell_{0}-1,
of PP are pairwise distinct.
Furthermore, we consider the integer sequence
yn=i=0k00dixn+i,n=1,2, \begin{equation*} y_{n}=\sum_{i=0}^{k_{0} \cdot \ell_{0}} d_{i} x_{n+i}, \quad n=1,2, \ldots \end{equation*}
By the theory of linear recursions, we obtain
yn=k,0kk0 or 0ek,(abakb)n,n=1,2,, \begin{equation*} y_{n}=\sum_{\substack{k, \ell \geq 0 \\ k \geq k_{0} \text{ or } \ell \geq \ell_{0}}} e_{k, \ell}\left(\frac{\sqrt{a b}}{a^{k} b^{\ell}}\right)^{n}, \quad n=1,2, \ldots, \end{equation*}
with real numbers ek,e_{k, \ell}. We have
ynk,0kk0 or 0ek,(abakb)n=:Mn. |y_{n}| \leq \sum_{\substack{k, \ell \geq 0 \\ k \geq k_{0} \text{ or } \ell \geq \ell_{0}}}|e_{k, \ell}|\left(\frac{\sqrt{a b}}{a^{k} b^{\ell}}\right)^{n}=: M_{n} .
Because the series in (4) is obtained by a finite linear combination of the absolutely convergent series (1), we conclude that in particular M1<M_{1}<\infty. Since
abakbλ:=max{abak0,abb0} for all k,0 such that kk0 or 0, \frac{\sqrt{a b}}{a^{k} b^{\ell}} \leq \lambda:=\max \left\{\frac{\sqrt{a b}}{a^{k_{0}}}, \frac{\sqrt{a b}}{b^{\ell_{0}}}\right\} \quad \text{ for all } k, \ell \geq 0 \text{ such that } k \geq k_{0} \text{ or } \ell \geq \ell_{0},
we get the estimates Mn+1λMn,n=1,2,M_{n+1} \leq \lambda M_{n}, n=1,2, \ldots. Our choice of k0k_{0} and 0\ell_{0} ensures λ<1\lambda<1, which implies Mn0M_{n} \rightarrow 0 and consequently yn0y_{n} \rightarrow 0 as nn \rightarrow \infty. It follows that yn=0y_{n}=0 for all sufficiently large nn.
So, equation (3) reduces to i=0k00dixn+i=0\sum_{i=0}^{k_{0} \cdot \ell_{0}} d_{i} x_{n+i}=0.
Using the theory of linear recursions again, for sufficiently large nn we have
xn=k=0,=0k01,01fk,(abakb)n x_{n}=\sum_{k=0, \ell=0}^{k_{0}-1, \ell_{0}-1} f_{k, \ell}\left(\frac{\sqrt{a b}}{a^{k} b^{\ell}}\right)^{n}
for certain real numbers fk,f_{k, \ell}.
Comparing with (2), we see that fk,=ck,f_{k, \ell}=c_{k, \ell} for all k,0k, \ell \geq 0 with k<k0,<0k<k_{0}, \ell<\ell_{0}, and ck,=0c_{k, \ell}=0 if kk0k \geq k_{0} or 0\ell \geq \ell_{0}, since we assumed that aμbνa^{\mu} \neq b^{\nu} for all positive integers μ,ν\mu, \nu.
In view of (1), this means
(1α)12(1β)12=k=0,=0k01,01ck,αkβ \begin{equation*} (1-\alpha)^{\frac{1}{2}}(1-\beta)^{\frac{1}{2}}=\sum_{k=0, \ell=0}^{k_{0}-1, \ell_{0}-1} c_{k, \ell} \cdot \alpha^{k} \beta^{\ell} \end{equation*}
for all real numbers α,β(0,1)\alpha, \beta \in(0,1). We choose k<k0k^{*}<k_{0} maximal such that there is some ii with ck,i0c_{k^{*}, i} \neq 0. Squaring (5) and comparing coefficients of α2kβ2i\alpha^{2 k^{*}} \beta^{2 i^{*}}, where ii^{*} is maximal with ck,i0c_{k^{*}, i^{*}} \neq 0, we see that k=0k^{*}=0. This means that the right hand side of (5) is independent of α\alpha, which is clearly impossible.
We are left with the case that aμ=bνa^{\mu}=b^{\nu} for some positive integers μ\mu and ν\nu. We may assume that μ\mu and ν\nu are relatively prime. Then there is some positive integer cc such that a=cνa=c^{\nu} and b=cμb=c^{\mu}. Now starting with the expansion (2), i.e.,
xn=j0gj(cμ+νcj)n x_{n}=\sum_{j \geq 0} g_{j}\left(\frac{\sqrt{c^{\mu+\nu}}}{c^{j}}\right)^{n}
for certain coefficients gjg_{j}, and repeating the arguments above, we see that gj=0g_{j}=0 for sufficiently large jj, say j>j0j>j_{0}. But this means that
(1xμ)12(1xν)12=j=0j0gjxj \left(1-x^{\mu}\right)^{\frac{1}{2}}\left(1-x^{\nu}\right)^{\frac{1}{2}}=\sum_{j=0}^{j_{0}} g_{j} x^{j}
for all real numbers x(0,1)x \in(0,1). Squaring, we see that
(1xμ)(1xν) \left(1-x^{\mu}\right)\left(1-x^{\nu}\right)
is the square of a polynomial in xx. In particular, all its zeros are of order at least 22, which implies μ=ν\mu=\nu by looking at roots of unity. So we obtain μ=ν=1\mu=\nu=1, i.e., a=ba=b, a contradiction.

Solution 2

We set a2=A,b2=Ba^{2}=A, b^{2}=B, and zn=(An1)(Bn1)z_{n}=\sqrt{(A^{n}-1)(B^{n}-1)}. Let us assume that znz_{n} is an integer for n=1,2,n=1,2, \ldots Without loss of generality, we may suppose that b<ab<a. We determine an integer k2k \geq 2 such that bk1a<bkb^{k-1} \leq a<b^{k}, and define a sequence γ1,γ2,\gamma_{1}, \gamma_{2}, \ldots of rational numbers such that
2γ1=1 and 2γn+1=i=1nγiγni for n=1,2, 2 \gamma_{1}=1 \quad \text{ and } \quad 2 \gamma_{n+1}=\sum_{i=1}^{n} \gamma_{i} \gamma_{n-i} \text{ for } n=1,2, \ldots
It could easily be shown that γn=113(2n3)2462n\gamma_{n}=\frac{1 \cdot 1 \cdot 3 \ldots(2 n-3)}{2 \cdot 4 \cdot 6 \ldots 2 n}, for instance by reading Vandermonde's convolution as an equation between polynomials, but we shall have no use for this fact.
Using Landau's OO-Notation in the usual way, we have
{(ab)nγ1(ab)nγ2(ab3)nγk(ab2k1)n+O(ba)n}2=AnBn2γ1Ani=2k(2γij=1i1γjγij)(ABi1)n+O(ABk)n+O(Bn)=AnBnAn+O(Bn) \begin{aligned} & \left\{(a b)^{n}-\gamma_{1}\left(\frac{a}{b}\right)^{n}-\gamma_{2}\left(\frac{a}{b^{3}}\right)^{n}-\cdots-\gamma_{k}\left(\frac{a}{b^{2 k-1}}\right)^{n}+O\left(\frac{b}{a}\right)^{n}\right\}^{2} \\ & =A^{n} B^{n}-2 \gamma_{1} A^{n}-\sum_{i=2}^{k}\left(2 \gamma_{i}-\sum_{j=1}^{i-1} \gamma_{j} \gamma_{i-j}\right)\left(\frac{A}{B^{i-1}}\right)^{n}+O\left(\frac{A}{B^{k}}\right)^{n}+O\left(B^{n}\right) \\ & =A^{n} B^{n}-A^{n}+O\left(B^{n}\right) \end{aligned}
whence
zn=(ab)nγ1(ab)nγ2(ab3)nγk(ab2k1)n+O(ba)n. z_{n}=(a b)^{n}-\gamma_{1}\left(\frac{a}{b}\right)^{n}-\gamma_{2}\left(\frac{a}{b^{3}}\right)^{n}-\cdots-\gamma_{k}\left(\frac{a}{b^{2 k-1}}\right)^{n}+O\left(\frac{b}{a}\right)^{n} .
Now choose rational numbers r1,r2,,rk+1r_{1}, r_{2}, \ldots, r_{k+1} such that
(xab)(xab)(xab2k1)=xk+1r1xk+±rk+1, (x-a b) \cdot\left(x-\frac{a}{b}\right) \ldots\left(x-\frac{a}{b^{2 k-1}}\right)=x^{k+1}-r_{1} x^{k}+\cdots \pm r_{k+1},
and then a natural number MM for which Mr1,Mr2,Mrk+1M r_{1}, M r_{2}, \ldots M r_{k+1} are integers. For known reasons,
M(zn+k+1r1zn+k+±rk+1zn)=O(ba)n M\left(z_{n+k+1}-r_{1} z_{n+k}+\cdots \pm r_{k+1} z_{n}\right)=O\left(\frac{b}{a}\right)^{n}
for all nNn \in \mathbb{N} and thus there is a natural number NN which is so large, that
zn+k+1=r1zn+kr2zn+k1+rk+1zn z_{n+k+1}=r_{1} z_{n+k}-r_{2} z_{n+k-1}+\cdots \mp r_{k+1} z_{n}
holds for all nNn \geqslant N. Now the theory of linear recursions reveals that there are some rational numbers δ0,δ1,δ2,,δk\delta_{0}, \delta_{1}, \delta_{2}, \ldots, \delta_{k} such that
zn=δ0(ab)nδ1(ab)nδ2(ab3)nδk(ab2k1)n z_{n}=\delta_{0}(a b)^{n}-\delta_{1}\left(\frac{a}{b}\right)^{n}-\delta_{2}\left(\frac{a}{b^{3}}\right)^{n}-\cdots-\delta_{k}\left(\frac{a}{b^{2 k-1}}\right)^{n}
for sufficiently large nn, where δ0>0\delta_{0}>0 as zn>0z_{n}>0. As before, one obtains
AnBnAnBn+1=zn2={δ0(ab)nδ1(ab)nδ2(ab3)nδk(ab2k1)n}2=δ02AnBn2δ0δ1Ani=2i=k(2δ0δij=1j=i1δjδij)(ABi1)n+O(ABk)n. \begin{aligned} & A^{n} B^{n}-A^{n}-B^{n}+1=z_{n}^{2} \\ & =\left\{\delta_{0}(a b)^{n}-\delta_{1}\left(\frac{a}{b}\right)^{n}-\delta_{2}\left(\frac{a}{b^{3}}\right)^{n}-\cdots-\delta_{k}\left(\frac{a}{b^{2 k-1}}\right)^{n}\right\}^{2} \\ & =\delta_{0}^{2} A^{n} B^{n}-2 \delta_{0} \delta_{1} A^{n}-\sum_{i=2}^{i=k}\left(2 \delta_{0} \delta_{i}-\sum_{j=1}^{j=i-1} \delta_{j} \delta_{i-j}\right)\left(\frac{A}{B^{i-1}}\right)^{n}+O\left(\frac{A}{B^{k}}\right)^{n} . \end{aligned}
Easy asymptotic calculations yield δ0=1,δ1=12,δi=12j=1j=i1δjδij\delta_{0}=1, \delta_{1}=\frac{1}{2}, \delta_{i}=\frac{1}{2} \sum_{j=1}^{j=i-1} \delta_{j} \delta_{i-j} for i=2,3,,k2i=2,3, \ldots, k-2, and then a=bk1a=b^{k-1}. It follows that k>2k>2 and there is some PQ[X]P \in \mathbb{Q}[X] for which (X1)(Xk11)=P(X)2(X-1)(X^{k-1}-1)= P(X)^{2}. But this cannot occur, for instance as Xk11X^{k-1}-1 has no double zeros. Thus our
assumption that znz_{n} was an integer for n=1,2,n=1,2, \ldots turned out to be wrong, which solves the problem.

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.