A set, product of any two elements minus one is a perfect square

Question

The first problem of IMO 1986 asks the following:

Prove that, one can find two distinct $a,b$ in the set $\{2,5,13,d\}$ such that $ab-1$ is not a perfect square.

Note that, this proves, for the set $S=\{2,5,13\}$, and for any distinct $x,y\in S$, $xy-1$ is a perfect square, and that, adding any other element to $S$ violates the condition.

Now, the natural question is the following. What is the largest $n$, for which, there exists a set $\{x_1,\dots,x_n\}$ of distinct positive integers, for which, $x_ix_j -1$ is always a perfect square? Clearly, $n\geq 3$, due to the argument above.

Remark : This problem arised as a post in AoPS forums, currently having no (useful) replys.

Answer 1

In this particular case it is easy to prove that for any $d \in \Bbb N$ at least one of $\{2d-1,5d-1,13d-1\}$ is not a perfect square. Let's rephrase the problem as:

Prove that there does not exist a $4$-tuple of positive integers $\{d,x,y,z\}$ such that $$ 2d-1 = x^2\\ 5d-1 = y^2 \\ 13d-1 = z^2 $$

Proof by contradiction: Let $\{d,x,y,z\}$ be such a $4$-tuple. Then:

$x$ is odd: $2d-1 = x^2\implies \exists t \in \Bbb N : x = 2t+1$. The first equation then reduces to $$ d = 2t^2 - 2t + 1 $$ and the second equation becomes $$ 10t^2 - 10 t + 4 = y^2 \\ \implies \exists u \in \Bbb N : y = 2u $$ The second equation then reduces to $5 t^2 - 5t + 2 = 2u^2$. Considering that equation in mod $5$ we see that $u^2 = 1 \pmod{5} \implies \exists v \in \Bbb N : u = 5v \pm 1$. Here we have used the fact that the only two square roots of $1$ in mod 5 are $1$ and $4 \equiv -1$.

Letting $u = 5v \pm 1$ we have $$ 5 t^2 - 5t + 2 = 2u^2 \implies 5 t^2 - 5t + 2 = 50 v^2 \pm 20 v + 2 \\ t^2 - t = 10 v^2 \pm 4v \\ d= 2(t^2-t)+1 = 20v^2 \pm 8v + 1 $$ Substituting this $d$ into the third equation we obtain $$ 13 d - 1 = z^2 \\ 260 v^2 \pm 104 v +13 -1 = z^2 $$ So $z$ is even and writing $z=2w$ we have $$ 65v^2 \pm 26v + 3 = w^2 $$ and considering this mod $13$ we have (A) $w = 13 r -4$ or (B) $w = 13r-9$.

(A) $w = 13 r -4$ leads to $$ 5v^2\pm 2v = 13r^2-8r+1 $$ In this equation, either $v$ (and hence the LHS) is even and $r$ is odd, or $v$ is odd, both sides of the equation are odd and $r$ must be even. If $v$ is even let $v=2k$ and $r = 2m-1$, then the equation becomes $$ 10k^2\pm 2k-26m^2+34m = 11 $$ which is impossible since the LHS is even. If If $v$ is odd, let $v=2k-1$ and $r = 2m$, then the equation becomes $$ 10k^2 + (\pm 2 - 10)k-26m^2+8m = 2\mp 1 $$ which again is impossible since the LHS is even and the RHS is odd. So case (A) does not lead to any solutions.

(B) $w = 13 r -9$ leads to $$ 5v^2\pm 2v = 13r^2-18r+6 $$ In this equation, either $v$ (and hence the LHS) is even and $r$ is even, or $v$ is odd, both sides of the equation are odd and $r$ must be odd. If $v$ is even let $v=2k$ and $r = 2m$, then the equation becomes $$ 10k^2\pm 2k-26m^2+18m = 3 $$ which is impossible since the LHS is even. If If $v$ is odd, let $v=2k-1$ and $r = 2m-1$, then the equation becomes $$ 10k^2 + (\pm 2 - 10)k-26m^2+44m = 16 \mp 1 $$ which again is impossible since the LHS is even and the RHS is odd. So case (B) does not lead to any solutions either.

Therefore, there does not exist a $4$-tuple of positive integers $\{d,x,y,z\}$ such that $$ 2d-1 = x^2\\ 5d-1 = y^2 \\ 13d-1 = z^2 $$ and this is what we set out to prove.

---

I must admit that if given this problem in a timed contest setting today, I would probably miss it. But back in 1986 it would have been one of the easy ones.

However, I now see that this does not answer the real question, which is how far you can go and always have all the pairs yield squares when you form $ab-1$.

Answer 2

The system of Diophantine equations like $$\begin{cases} 2d-1 = x^2\\ 5d-1 = y^2 \\ 13d-1 = z^2 \end{cases}$$ can be systematically computationally solved by considering an equivalent system (with eliminated $d$): $$\begin{cases} 5 x^2 - 2 y^2 = -3\\ 13x^2 - 2 z^2 = -11 \end{cases}$$ and using Theorem 6 from this paper of mine. This particular system happens to have no solutions.