Hamper.r wrote: a, a_1,a_2,...,a_n are natural numbers. We know that for any natural number k which ak+1 is square, at least one of a_1 k+1,...,a_n k+1is also square. Prove "a" is one of a_1,...,a_n . $a, a_1,a_2,\dots ,a_n$ are natural numbers. We know that for any natural number $k$ which $ak+1$ is square, at least one of $a_1k+1,\dots ,a_n k+1$ is also square. Prove $a$ is one of $a_1,\dots ,a_n$. FTFY....

Hamper.r wrote: Let $a, a_1,a_2,\dotsc ,a_n$ be natural numbers such that for any natural number k which $ak+1$ is a square, at least one of $a_1 k+1,\dotsc ,a_n k+1$ is also a square. Prove that $a$ is one of $a_1,\dotsc ,a_n$. Suppose to the contrary that $a\neq a_i$ for all $i$. Let $M=\max \{ 2,a,a_1,a_2,\dotsc ,a_n\}$. Lemma: For any integer $t_1,t_2\neq 0$, there exist infinitely many prime $p\nmid t_1t_2$ that $\left( \frac{t_1}{p}\right) =\left( \frac{t_2}{p}\right) =1$. Proof: There exists infinitely many prime $p$ that $p\equiv 1\pmod{8t_1t_2}$. Now, back to the problem. For any $i=1,2,\dotsc ,n$, there exists prime $p_i>M$ that $\left( \frac{a_i-a}{p_i}\right) = \left( \frac{a_i}{p_i}\right) =1$. Also, we can select $p_i$s so that $p_1,p_2,\dotsc ,p_n$ are pairwise distinct. This means there exists integer $n_i$ that $n_i^2\equiv a_i-a\pmod{p_i}$. Moreover, we can select such $n_i$ so that $p_i^2\nmid n_i^2-(a_i-a)$ (by considering $n_i$ and $n_i+p_i$). In other words, there exists integer $c_i$ that $n_i^2\equiv ac_ip_i+(a_i-a)\pmod{p_i^2}$ and $p_i\nmid c_i$. Now, by CRT, there exists positive integer $k$ that $a_ik+1\equiv c_ip_i\pmod{p_i^2}$ for all $i$. Moreover, there exists $K$ and $P=p_1p_2\cdots p_n$ such that all $k$ that $k\equiv K\pmod{P^2}$ satisfy the above condition. For all $i$, we have $aK+1\equiv a\cdot (c_ip_i-1)a_i^{-1}+1\pmod{p_i^2}$ where $a_i^{-1}$ is the inverse of $a_i$ modulo $p_i^2$. We have $a\cdot (c_ip_i-1)a_i^{-1}+1 \equiv (ac_ip_i-a+a_i)a_i^{-1}\pmod{p_i^2}$. Note that $\left( \frac{a_i^{-1}}{p_i}\right) \left( \frac{a_i}{p_i}\right) =1\implies \left( \frac{a_i^{-1}}{p_i}\right) =1$ and $n_i^2\equiv ac_ip_i+(a_i-a)\pmod{p_i^2}$. We get that there exists $N_i$ that $aK+1\equiv N_i^2\pmod{p_i^2}$. By CRT, there exists positive integer $x$ that $x\equiv N_i\pmod{p_i^2}$ for all $i$ and $x\equiv 1\pmod{a}$. We get $x^2\equiv aK+1\pmod{aP^2}$, so there exists $m$ that $a(P^2m+K)+1$ is a perfect square. But for any $i$, $a_i(P^2m+K)+1\equiv a_iK+1\equiv a_ik+1\equiv c_ip_i\pmod{p_i^2}\implies \nu_{p_i} (a_i(P^2m+K)+1)=1$. So, none of $a_i(P^2m+K)+1$ is a perfect square. Contradiction.

Suppose that $a_i \neq a$ for all $i,$ and let $d_i=a_i-a.$ Clearly, none of the $d_i$'s is zero. For any $m$ we have that $ak+1$ is a perfect square, where $k=m(am+2),$ thus there exists a $0\le j\le n$ and an integer $t,$ such that $$(am+1)^2+d_jm(ma+2)=(am+t)^2 \Longleftrightarrow$$$$d_jm(ma+2)=(t-1)(2am+t+1) \Longleftrightarrow d_j=\frac{(t-1)(2am+t+1)}{m(am+2)}$$Let $m$ be any odd prime, then $t$ has the form $pc+1$ or $pc-1.$ Suppose that $t=pc+1 \implies$ $$\frac{c(2ap+pc+2)}{ap+2}=d_j \Longleftrightarrow \frac{c(pc-2)}{ap+2} \in \mathbb{Z}$$Let $d=\gcd(ap+2, pc-2) \implies d \mid ap+2+pc-2 \implies d\mid a+c \implies d\le a+c. $ $$\frac{c(pc-2)}{ap+2} \in \mathbb{Z} \Longleftrightarrow \frac{c}{\frac{ap+2}{d}} \in \mathbb{Z} \Longleftrightarrow \frac{cd}{ap+2} \in \mathbb{Z} \implies c(a+c) \ge cd \ge ap+2 \implies c\ge \sqrt{p}$$Thus, $d_j=\frac{c(2ap+pc+2)}{ap+2} > \sqrt{p},$ which is not true for large enough $p$. Analogously, if $t=pc-1,$ then $d_j=\frac{(pc-2)(2a+c)}{ap+2},$ thus $(a+c)(2a+c) \ge 2ap+2,$ which again implies a contradiction.

If $a_i \neq a$ for all $i=1,2,...,n$, let $k=l(la+2)$, then $aa_{i}l^2+2la_i+1=y^2$, $aa_{i}(la+1)^2-a^2x^2=a(a_i-a)$. if $aa_i$ is a perfect square, we know two continuous perfect squares' distance is lagre enough when they are lagre enough, but $a(a_i-a)$ is finite, a contradiction. If $aa_i$ is not a perfect square, $aa_{i}l^2+2la_i+1=y^2$, $aa_{i}(la+1)^2-a^2x^2=a(a_i-a)$ is $n$ pell equations, $i=1,2,...,n$. If the equation is without solution, we have done. If it has solutions, we select $N$ is lagre enough, the number of whose form in $1,2,...,N$ is $la+1$ is at least $[\frac{N}{a}]$, but those pell equations' solutions is exponential growth, the density is less than $\frac{1}{a}$, a contradiction.

Solution by Azerbaijan team: Choose $k=m (am+2) $ and $m $ odd prime.So one of $a_i $'s say $b $ has the following property: $p_i^2\cdot ab+2p_i\cdot b+1=x_i^2$ .WLOG for infinitely many of $i $'s $x_i=p_i\cdot k_i+1$ Then we easily get that $p_i (k_i^2-ab)=2 (k_i-b)$ $\implies$ $p_i|k_i-b $ then define $c_i=\frac {k_i-b}{p_i}$ , from above divisiblities we can get that $c_i|b (a-b) $ so if $a\neq b $ $c_i $'s are equal for infinitely many values of $i $.But $c_i=\frac {k_i-b}{p_i}=\frac {k_i^2-ab}{2}$ so $k_i $'s are same for these values of $i $ then $p_i $'s are same but the primes we've choosen are different.contradiction.

Here's my Solution. Lets suppose the conclusion is false. Let $N = a_1 a_2 \cdots a_n$ $P_i$ is one of the prime factors of $a_i (a_i - a)( N P_1 P_2 \cdots P_{i-1} )^2 - 1$ . This definition guarantees that $P_i$s are different from each other, $\left( \frac{1-a a_i ^* }{P_i}\right)=\left( \frac{a_i^* (a_i - a)}{P_i}\right)=\left( \frac{(a_i (a_i - a))^* }{P_i}\right)=1$ ($a^*$ is an arithmethic inverse of a in $(mod P_i ^2)$) , and $gcd(P_i ,a a_i)=1$. Set $k_i$ an integer which satisfies $a_i k_i + 1 \equiv a^* a_i P_i (mod P_i ^2)$ $\Rightarrow ak_i +1 \equiv a(a_i ^* (a^* a_i P_i -1))+1 \equiv P_i + (1-a a_i ^*) (mod P_i ^2)$ by Hensel's Lemma and the Legendre Symbol calculated above, There exists an integer $t_i$ that satisfies $t_i ^2 \equiv P_i + (1-a a_i ^*) (mod P_i ^2)$. Let $\forall i , K \equiv k_i (mod P_i ^2) , T \equiv t_i (mod P_i ^2)$. $\Rightarrow a_i K +1 \equiv a^* a_i P_i (mod P_i ^2)$ , $a K + 1 \equiv T^2 (mod P_1 ^2 P_2 ^2 \cdots P_n ^2)$ , which guarantees the existance of integer $K ^\prime$ , which satisfies $K ^\prime \equiv K (mod P_1 ^2 P_2 ^2 \cdots P_n ^2) , a K ^\prime+1$ is a perfect square , and $a_i K ^\prime + 1$ not be a perfect square . This makes contradiction to the supposition, and we are done.

Is this solution correct too? assume ai, i€{1,..,n} is such that ai*k+1 is perfect square, then, ai*k+1=p^2 a*k+1=q^2 So. (ai—a)*k=(p+q)*(p-q).. Take k to be prime, then we have 2 cases, and these are true for any k€N(as p+q, p-q are integers) Case 1: 4|(ai-a) Put p+q=2*k1 and p-q=2*k2, then ai—a=4*k1*k2,p=k1+k2 and q=k1-k2.. Now take k=p+q€N We have, ai—a=p-q or, 4k1*k2=2k2 or, k2=0 Hence p=q and a=ai Case 2: (a-ai) is odd... This is not worth discussing as. Putting k, s.t. k has only one power of two... Contradicts the facts that p, q are integers (as (a-ai)*k is non factorisable)

Lemma :Let $a$ be a natural number which is not a perfect square. Then there exist infinitely many prime numbers $p$ such that $p \equiv 3 ( mod 4 ) $ and there exist a natural number $x$ such that $p | ax^2+1$. Proof: Suppose that for distinct primes $p_1 , ... , p_t$ and $y \in \mathbb{N}$ we have $a=p_1...p_ty^2$ , so we want to show that there exist primes $q$ in the form $4k+3$ such that for a natural $x$ we have : $x^2 \equiv -p_1^*...p_t^*$ $(mod q)$ $\iff \prod\left(\frac{-p_i^*}{q}\right)=1 \iff \prod\left(\frac{p_i}{q}\right)=(sgn)1 $ which sgn of 1 will determine uniquely based on $p_i$ values mod $4$. So by quadratic reciprocity , it's enough to find a prime $q$ in the form $4k+3$ such that : $ \prod\left(\frac{q}{p_i}\right)=(sgn)1$ So if $sgn:+$ , then by Dirichlet theorem there is infinitely many prime numbers $q$ such that $q \equiv 1$ $( mod p_1...p_t)$ and $q \equiv 3$ $(mod 4)$ which works in the equality. And if $sgn:-$ , then take $a$ as a quadratic nonresidue modulo $p_1$ and let $q$ in form $4k+3$ be $q \equiv a$ $( mod p_1)$ and $q \equiv 1$ $( mod p_2...p_t)$. So the lemma is proved in both cases. Now firstly one can suppose that for each $a_i$ , there exist infinitely many natural $k$ such that $ak+1$ and $a_ik+1$ are both squares ( ignoring others ! ). So we will show that there exist a number $a_i$ , such that $aa_i$ is a perfect square. Suppose not , notice that for each integer $t$ , if we take $k_t=at^2+2t$ then $ak_t+1$ is a perfect square. Now by lemma for each $i$ , there exist infinitely many primes $q_1 , q_2 , ...$ in form $4k+3$ and numbers $r_1 , r_2 , ...$ , such that for each $j$ and $x \equiv r_j$ $(mod q_j)$ we have $q_j | aa_ix^2+1$. so for each number $t \equiv r_j$ $(mod q_j)$ , numbers $a_ik_t+1$ and $a_ik_{-t}+1$ can't both be squares , otherwise we have : $a_ik_t+1=x^2$ , $a_ik_{-t}+1=y^2$ $\implies 2(aa_it^2+1)=x^2+y^2 \implies q_j | x^2+y^2 \implies q_j | x , y \implies q_j | gcd(4a_it , aa_it^2+2a_it+1)|4. $ which is a contradiction. so for each $q_j$ , there exist a number $s_j$ ( equals to $r_j$ or $-r_j$ modulo $q_j$ ) such that for each $t \equiv s_j$ $(mod q_j)$ , number $a_ik_t+1$ is not a perfect square. Now consider distinct primes $q_1 , ... q_n$ for $a_1 , ... , a_n$ ( which is possible because of the infinity. ) and by CRT take a natural $t$ such that $t \equiv s_i$ $(mod q_i)$ for each $i \le n$ and none of the numbers $a_ik_t+1$ will be a perfect square. So there is a $i$ such that $aa_i$ is square , let $aa_i=s_i^2$ and the number $s_i^2t^2+2a_it+1$ will be a square for infinitely many natural $t$ and $s_i^4t^2+2s_i^2a_it+s_i^2$ and $(s_i^2t+a_i)^2$ are both squares , so there are big enough squares with a constant distance $s_i^2-a_i^2$. as the result , $s_i^2=a_i^2$ and $a=a_i$. So we're done.

Assume not. We will construct a $k$ of the form $k=ax^2+2x$ such that the statement does not hold. The proof hinges on the following two folklore lemmas. Lemma 1: Let $P$ be a polynomial. If $P(x)$ is a perfect square for every integer $x$, then $P$ itself is the square of a polynomial. Pf: See here. $\blacksquare$ Lemma 2: If $N$ is not a perfect square, then there exist infinitely many primes $p$ such that $\left(\frac{N}{p}\right)=-1$. Pf: See here $\blacksquare$ Consider the $n$ polynomials $$P_i(x)=a_ia x^2+2a_ix+1\in \mathbb{Z}[x] \text{ for } 1\leq i \leq n-1.$$By our assumption, none of them is the square of a linear polynomial. Hence by Lemma 1, for each $1\leq i \leq n-1$ there exists an integer $x_i$ such that $P(x_i)$ is not a perfect square. By Lemma 2, there will exist a prime $p_i$ such that $P(x_i)$ is not a quadratic residue mod $p_i$ (notice that we may, and should assume that all $p_i$ are diferent). Now, by CRT we may solve the following system of congruences: $$X\equiv x_i\pmod{p_i} \text{ for each } 1\leq i \leq n-1,$$constructing an $X$ such that $P_i(X)$ can never be a perfect square, for no $1\leq i \leq n-1$. Hence our assumption was false, and the problem is solved.

hmm, this solution seems different from the ones above:

If $k = ax^2 + 2x$, then $ak+1$ is a perfect square. So we have that for all positive integers $x$, there exists an $i$ such that $aa_ix^2 + 2xa_i + 1 = N^2 \implies xa_i(ax+2) = (N+1)(N-1)$. Specialize to the choice of $x = p$ being prime. Then we must have some $i$, wlog assume $a_1$ such that the equation is true for infinitely many primes. $$pa_1(ap+2) = (N+1)(N-1)$$Note that $N \equiv \pm 1 \pmod p$, but also $\frac{N}{p}$ is bounded above by $\sqrt{aa_1}$ so since we have infinitely many values, there must exist some $m$ such that $N = mp \pm 1$ for infinitely many values. This gives that $pa_1(ap+2) = mp(mp \pm 2) \implies aa_1p + 2a_1 = m^2p \pm 2m$. As this is true for infinitely many primes $p$, this forces that $m^2 = aa_1$ and $2a_1 = \pm 2m$, clearly the second can only hold with positive sign, implying $m = a_1$. So together, we get $a_1 = a$, as desired. $\blacksquare$

WypHxr wrote: the density is less than $\frac{1}{a}$, a contradiction. It's good to know, by Siegel theorem it's density is zero!