Consider a nonconstant arithmetic progression $a_1, a_2,\cdots, a_n,\cdots$. Suppose there exist relatively prime positive integers $p>1$ and $q>1$ such that $a_1^2, a_{p+1}^2$ and $a_{q+1}^2$ are also the terms of the same arithmetic progression. Prove that the terms of the arithmetic progression are all integers.
Problem
Source: INMO 2016 Problem 6
Tags: arithmetic sequence, number theory, relatively prime, number theory proposed
17.01.2016 15:46
Hint: First prove that $a_1$ and common difference are rational... (Mine is a very long and boring solution)
17.01.2016 16:01
after proving that wat did you prove that they are integers??
17.01.2016 16:03
Yep, this was hard... i wrote down the rational part, and then I had some bad equations which were just not yielding.. :O
17.01.2016 16:11
very same with me
17.01.2016 16:22
I proved by considering v10(a1),v10(a1^2),v10(ap+1^2) and v10(aq+1^2)
17.01.2016 16:29
TheOneYouWant wrote: Yep, this was hard... i wrote down the rational part, and then I had some bad equations which were just not yielding.. :O After that take gcd of denominators and use some divisibility arguments...
17.01.2016 17:35
What do I have to do when I prove that the race and a1 are rationals? I cannot see..
17.01.2016 17:49
Those who solved the problem...anyone?
17.01.2016 17:56
I wrote a few divisibility arguments.. how much do you think this is worth?
17.01.2016 17:58
Well, did you finish the problem?If yes, maximum points. Else, i don't know.; if this is what you mean. I still haven't finished this problem...
17.01.2016 18:04
No, i did not finish the problem. What i did was: A) wrote the usual equations B) proved rationality of A1 and D, thus rationality of the sequence C) rewrote A1 = A/X, D = B/X and then got some divisibilities like X|so and so
17.01.2016 18:10
I obtained : $$a_1+xm/n=a_1^2$$$$y-x=p^2m/n+2a_1p$$$$z-x=q^2m/n+2a_1q$$$z,x,y,p,q \in\mathbb Z $ $m/n$ is the race $a_1$ is the first term of the sequence. Then ?
17.01.2016 18:15
Does anybody have the solutions of the contest...? Can someone post this solution here, since those who said they solved it haven't posted it yet here..
17.01.2016 21:43
Let $a_n = a + (n - 1)d$ for some $a, d$(guessing they are complex numbers). Suppose $a_1^2 = a_{u + 1}, a_{p + 1}^2 = a_{v + 1}, a_{q + 1}^2 = a_{w + 1}$ for some integers $u, v, w \ge 0$. Then, $a^2 = a + ud$ and $(a + pd)^2 = a + vd \Longrightarrow p^2d^2 + 2apd = (u + v)d$ and since $d \neq 0$, $p^2d + 2ap = u + v$. Similarly, $q^2d + 2aq = u + w$. From these, we get $pq(p - q)d = q(u + v) - p(u + w)$. Since $p > 1$ and $q > 1$ and $(p, q) = 1$, we have $p \neq q$ and so, the last equation shows that $d$ is rational as $p, q, u, v$ are integers. Then, $a = \frac{u + v - p^2d}{2p}$ is also rational. Let $a = \frac{x}{y}, d = \frac{z}{w}$ where $y > 0, w > 0, (x, y) = (z, w) = 1$. Let $g = (y, w), \alpha = x\left(\frac{w}{g}\right), \beta = z\left(\frac{y}{g}\right), L = y\left(\frac{w}{g}\right)$. Then, $\alpha, \beta, L \in \mathbb{Z}$ with $a = \frac{\alpha}{L}, d = \frac{\beta}{L}$. Now, $a^2 = a + ud \Longrightarrow \alpha^2 = L(\alpha + u\beta) \Longrightarrow L \mid \alpha^2$. We also have $p^2\beta + 2\alpha p = L(u + v)$ and $q^2\beta + 2\alpha q = L(u + w)$. So, $L \mid p^2\alpha\beta + 2\alpha^2p \Longrightarrow L \mid p^2 \alpha\beta$ as $L \mid \alpha^2$. Similarly, $L \mid q^2 \alpha\beta$. So, $L \mid (p^2\alpha\beta, q^2\alpha\beta) = \alpha\beta$ as $(p, q) = 1$. Now, $L \mid p^2\beta^2 + 2\alpha\beta p \Longrightarrow L \mid p^2\beta^2$ as $L \mid \alpha\beta$. Similarly, $L \mid q^2 \beta^2$ and so, $L \mid (p^2\beta^2, q^2\beta^2) = \beta^2$. Now, $L \mid \alpha^2 \Longrightarrow y\left(\frac{w}{g}\right) \mid x^2\left(\frac{w}{g}\right)^2 \Longrightarrow y \mid x^2\left(\frac{w}{g}\right)$ and since $(x, y) = 1$, we have $y \mid\left(\frac{w}{g}\right) \Longrightarrow gy \le w$ and $L \mid \beta^2 \Longrightarrow w\left(\frac{y}{g}\right) \mid z^2\left(\frac{y}{g}\right)^2 \Longrightarrow w \mid z^2\left(\frac{y}{g}\right)$ and $(w, z) = 1 \Longrightarrow w \mid\left(\frac{y}{g}\right) \Longrightarrow gw \le y$. So, multiplying them(as $y, w, g > 0$), $g^2yw \le yw \Longrightarrow g^2 \le 1$ and so, we have $g = 1$. Then, this gives $y \le w$ and $w \le y$ and so, $y = w$. Finally, $y = w = (y, w) = g = 1 \Longrightarrow y = w = 1$ and so, $a = x, d = z \in \mathbb{Z}$ as required.
17.01.2016 21:49
Thank you very much.
18.01.2016 02:28
This seems to have it's difficulty over-rated unless I am missing something. Let $a_1=a$ and $a_2-a_1=b$. It shall suffice to showing that both $a$ and $b$ are integers. Notice that the given conditions imply that there exists positive integers $n,m,k>1$ satisfying \begin{align*} a^2=a+nb \end{align*}\begin{align*} (a+pb)^2=a^2+2apb+p^2b^2=a+nb+2apb+p^2b^2=a+mb \end{align*}\begin{align*} (a+qb)^2=a^2+2aqb+q^2b^2=a+nb+2aqb+q^2b^2=a+kb \end{align*} These in turn provide that \begin{align*} (m-n)=p(2a+pb) \end{align*} \begin{align*} (k-n)=q(2a+qb) \end{align*} These two equations give that $a,b \in \mathbb{Q}$. It all comes down to proving that $a,b \in \mathbb{Z}$. Now, we know that $b=\frac{a(a-1)}{n}$ and so substituting this we get that \begin{align*} a[2apn+p^2(a-1)]=n(m-n) \end{align*}\begin{align*} a[2aqn+q^2(a-1)]=n(k-n) \end{align*} Now, substituting $a=\frac{x}{y}$ where $x,y \in \mathbb{Z}$ such that $(x,y)=1$ we get that \begin{align*} x[2pny+p^2(x-y)]=y^2n(m-n) \end{align*}\begin{align*} x[2qny+q^2(x-y)]=y^2n(k-n) \end{align*} Now, we see that these equations imply that $y \mid 2pny+p^2x-p^2y$ and so $y \mid p^2$. Analogously $y \mid q^2$. Thus, $y=1$ and so $a \in \mathbb{Z}$. Now, we know that \begin{align*} p^2b=m-n-2ap \in \mathbb{Z} \end{align*}\begin{align*} q^2b=k-n-2aq \in \mathbb{Z} \end{align*} Now, letting $b = \frac {u}{v}$ where $u,v \in \mathbb{Z}$ and $(u,v)=1$. Then we see that $v \mid p^2$ and $v \mid q^2$ and so $v=1$ which means that $b \in \mathbb{Z}$. Thus, the result holds.
24.08.2016 14:38
Mine Solution:(same like Anant bhaiya's solution) Let us write ${a_1}^2=a_1 +bd, a_{p+1}=a_1+pd, a_{q+1}=a_1+qd$ where $d$ is the common difference and $b, p, q$ are integers. Squaring the above equations ${a_{p+1}}^2=a_1^2+p^2d^2+2a_1pd$ Or ${a_{p+1}}^2=a_1+bd+p^2d^2+2a_1pd=a_1+d(b+p^2d+2a_1p)$ So $b+p^2d+2a_1p$ is an integer. $p^2d+2a_1p$ is an integer. Similarly $q^2d+2a_1q$ is an integer. ……………1 $pd+2a_1$ and $qd+2a_1$ are rationals. ……………………………………..2 Subtracting we get $(p-q)d$ is rational. Hence d is rational. Also by subtracting both the equations of 1 we get $(p-q)[(p+q)d+2a_1]$ is integer. So $a_{p+1}+a_{q+1}$ is rational. Also by adding both equations of 2 we get $a_{p+1}+a_{q+1}+2a_1$ is rational. Subtracting the above we get $2a_1$ is rational. Also $a_1^2- a_1$ is integer. And we can easily show that $a_1$ is integer. So we get $a_1$ as integer and $d$ as rational. As in the above step we get $p^2d+2a_1p$ is an integer, now $p^2d$ is integer. Also $q^2d$ is integer. Assume $d$ as a fraction of intergers and by using that $gcd(p,q)=1$ we also get $d$ as an integer. So all terms of AP are integer.
11.12.2017 16:44
My solution: Let $a$ be the 1st term and $d$ be the common difference. For some non-negative integers $x,y,z$,we have: $a^2=a+xd$ $(a+pd)^2=a+yd$ $(a+qd)^2=a+zd$ Hence, $a^2+2apd+p^2d^2=a+yd$ $a^2+2aqd+q^2d^2=a+zd$ $\implies a^2-a=xd=yd-2apd-p^2d^2=zd-2aqd-q^2d^2$ $\implies x=y-2ap-p^2d=z-2aq-q^2d$ Hence, $2ap+p^2d$ is integer,so, $2a+pd $ is rational. Similarly, $2a+qd$ is rational. Hence $(p-q)d$ is rational, $\implies d$ is rational. Hence, $a$ is also rational Let $d=\frac{m}{n}$, and $a=\frac{t}{u}$ with $n,u>0$ Hence, $y-x=2tp/u+p^2m/n$ $\implies nu(y-x)=2tpn+p^2mu$ $\implies n | p^2u$ and $u |2tpn$ Also, $ n | q^2u$ and $u |2tqn$ Since $(p,q)=1$ , we can chose numbers $x.y$, such that $px+qy=1$ The same as above can be done for $p^2,q^2$. Hence, by choosing such numbers, we get, $n|u$ and $u|2n$. Now,by $a^2-a=xd$, we get, $t^2/u^2-t/u=xm/n$ $\implies t^2n-tun=xmu^2$ $\implies u|t^2n$ Hence, $u|n$. Since $u|n$ and $n|u$, $n=u$ Substituting in $ t^2n-tun=xmu^2, we get, $t^2-tu=xmu$ Hence $u|t$, $\implies n=u=1$, as desired. So all terms of the AP are integers.
01.03.2021 18:00
Since $a^2$ is part of the progression, we see that $$a^2 = a + kd \qquad (1)$$Now $a_{p+1}^2 = (a + pd)^2 = a^2 + p^2d^2 + 2apd = a + kd + p^2d^2 + 2apd = a + d(k + p^2d + 2ap)$, which means $k + p^2d + 2ap \in \mathbb{Z}$, but since $k \in \mathbb{Z}$, $p^2d + 2ap \in \mathbb{Z}$. Hence $p(pd + 2a) \in \mathbb{Z} \implies pd + 2a \in \mathbb{Q}$. Analogously, $qd + 2a \in \mathbb{Q}$. Subtracting them shows $pd - qd \in \mathbb{Q} \implies d \in \mathbb{Q}$ since $p, q \in \mathbb{N}$. Furthermore, since $d$ is rational, and $p^2d + 2ap \in \mathbb{Z}$, it follows that $a \in \mathbb{Q}$. Since we have both $a, d$ are rational, we may write $a = \tfrac{w}{x}, d = \tfrac{y}{z}$ where $(w, x) = 1 = (y, z)$. From $(1)$, we see that $\tfrac{w^2}{x^2} = \tfrac{w}{x} + \tfrac{ky}{z}$. From $p^2d + 2ap \in \mathbb{Z}$, $\tfrac{p^2y}{z} + \tfrac{2pw}{x} \in \mathbb{Z} \implies xz \mid p^2xy + 2pwz \implies x \mid p^2xy + 2pwz, z \mid p^2xy + 2pwz$. Since $x \mid p^2xy$, it follows that $x \mid 2pwz \implies x \mid 2pz$ since $(w, x) = 1$. Analogously, $x \mid 2qz$. Observe that $(p, x) > 1 \implies (q, x) = 1$ and $(q, x) > 1 \implies (p, x) = 1$. WLOG assume that $(p, x) = 1$. So $x \mid 2pz \implies x \mid 2z$. Now from $z \mid p^2xy + 2pwz$, clearly $z \mid p^2xy$, but since $(y, z) = 1$, $z \mid p^2x, z \mid q^2x$. Once again, $(p, x) > 1 \implies (q, x) = 1$ and $(q, x) > 1 \implies (p, x) = 1$. Hence $z \mid x$. But $x \mid 2z, z \mid x \implies x = z$. So $(1)$ becomes $\tfrac{w^2}{x^2} = \tfrac{w}{x} + \tfrac{ky}{x} \implies \tfrac{w^2}{x} = w + ky \implies x \mid w^2 \implies x = 1$ since $(w, x) = 1$. So $a, d$ are integers and we are done.
03.02.2022 08:44
Terribly easy question: Let the common difference be $d$. Let $a_1^2=a_1+xd$...(1) $a_{p+1}^2=a_1+yd$....(2) $a_{q+1}^2=a_1+zd$....(3) Subtracting (1) from (2) and (3), $$p^2d+2ap=(y-x)$$$$q^2d+2aq=(z-x)$$These equations immediately show $a,d \in \mathbb{Q}$ Now in above two equations substitute $d=\frac{a(a-1)}{x}$ and $a=\frac{m}{n}$ and $\gcd(m,n)=1$ to get: $$m\{2pxn+(m-n)p^2\}=n^2x(y-x)$$....(A) $$m\{2qxn+(m-n)q^2\}=n^2x(z-x)$$....(B) Reducing equation (A) and (B) modulo $n$, we have $$m^2p^2 \equiv 0 \mod n \implies p^2 \equiv 0 \mod n$$Similarly from (B) we have $$q^2 \equiv 0 \mod n$$. Thus $\gcd(p,q) \neq 1$, a contradiction unless $n=1$. So $a=m \in \mathbb{Z}$. Again applying similar logic by taking $d$ in a rational form we find that $\text{denominator} | p^2$ and $\text{denominator} | q^2$ which holds iff $\text{denominator} = 1$. Hence $a,d \in \mathbb{Z}$ which necessarily implies it is an integer AP.
27.12.2023 09:29
anantmudgal09 wrote: This seems to have it's difficulty over-rated unless I am missing something. Let $a_1=a$ and $a_2-a_1=b$. It shall suffice to showing that both $a$ and $b$ are integers. Notice that the given conditions imply that there exists positive integers $n,m,k>1$ satisfying \begin{align*} a^2=a+nb \end{align*}\begin{align*} (a+pb)^2=a^2+2apb+p^2b^2=a+nb+2apb+p^2b^2=a+mb \end{align*}\begin{align*} (a+qb)^2=a^2+2aqb+q^2b^2=a+nb+2aqb+q^2b^2=a+kb \end{align*} These in turn provide that \begin{align*} (m-n)=p(2a+pb) \end{align*} \begin{align*} (k-n)=q(2a+qb) \end{align*} These two equations give that $a,b \in \mathbb{Q}$. It all comes down to proving that $a,b \in \mathbb{Z}$. Now, we know that $b=\frac{a(a-1)}{n}$ and so substituting this we get that \begin{align*} a[2apn+p^2(a-1)]=n(m-n) \end{align*}\begin{align*} a[2aqn+q^2(a-1)]=n(k-n) \end{align*} Now, substituting $a=\frac{x}{y}$ where $x,y \in \mathbb{Z}$ such that $(x,y)=1$ we get that \begin{align*} x[2pny+p^2(x-y)]=y^2n(m-n) \end{align*}\begin{align*} x[2qny+q^2(x-y)]=y^2n(k-n) \end{align*} Now, we see that these equations imply that $y \mid 2pny+p^2x-p^2y$ and so $y \mid p^2$. Analogously $y \mid q^2$. Thus, $y=1$ and so $a \in \mathbb{Z}$. Now, we know that \begin{align*} p^2b=m-n-2ap \in \mathbb{Z} \end{align*}\begin{align*} q^2b=k-n-2aq \in \mathbb{Z} \end{align*} Now, letting $b = \frac {u}{v}$ where $u,v \in \mathbb{Z}$ and $(u,v)=1$. Then we see that $v \mid p^2$ and $v \mid q^2$ and so $v=1$ which means that $b \in \mathbb{Z}$. Thus, the result holds. Bro, I also have a similar soln.