19
$\begingroup$

I could not find any existing questions on this site stating this problem. Therefore I am posting my solution and I ask for other ways to prove this theorem too.

The Question

Prove that there cannot be an infinite integer arithmetic progression of distinct terms all of which are perfect squares.

My attempt

We shall prove it using contradiction. First off, there are a couple of things to notice which greatly simplify our discussion:

  1. The AP cannot be decreasing as eventually, the terms will be negative and perfect squares are non-negative.
  2. There has to be a non-zero, positive difference between the terms otherwise the terms would not be distinct.

Let us therefore, assume an AP with the first term $a$ - a non-negative integer and the positive difference $d$. The $i$th term of the AP is $T_i=a+(i-1)d$.

The AP is increasing, therefore there is a term $T_n$ for the least value of $n$ such that $T_n\geq d^2$. Now, $T_{n+1}$ is also a perfect square. Let $T_{n+1}=b^2$. Therefore, we have $$ d^2 \leq b^2 \implies d \leq b $$

Therefore we have $$ T_{n+1}=b^2+d<b^2+2b+1=(b+1)^2 $$ or $$b^2 < T_{n+1} < (b+1)^2$$

However, there are no perfect squares between two consecutive perfect squares. This contradicts our supposition that every term is a perfect square and an integer at the same time. Therefore, no such arithmetic progression exists.

$\endgroup$
6
  • 5
    $\begingroup$ It looks perfect to me. $\endgroup$ Commented Feb 22, 2017 at 18:40
  • 2
    $\begingroup$ The proof looks fine. You could, if you like, not bother with asserting the existence of a least $n$ such that $T_n\ge d^2$, and instead just note that $T_{d+1}=a+d^2\ge d^2$, which will trap $T_{d+2}$ between $b^2=T_{d+1}$ and $(b+1)^2$. $\endgroup$ Commented Feb 22, 2017 at 18:54
  • 2
    $\begingroup$ I think it maybe it should say "Let $T_n=b^2$." $\endgroup$ Commented Feb 22, 2017 at 23:17
  • 1
    $\begingroup$ See also math.stackexchange.com/questions/1625113/… $\endgroup$ Commented Feb 23, 2017 at 5:05
  • 1
    $\begingroup$ @JonathanAllan No it's okay. $\endgroup$ Commented Feb 23, 2017 at 5:10

4 Answers 4

Reset to default
17
$\begingroup$

You can prove a slightly stronger result: Any arithmetic progression with all terms distinct can have at most a finite number of consecutive terms both of which are squares.

Proof: If $d\not=0$ is the difference between consecutive terms and $a^2$ and $b^2$ are two consecutive terms that are both square, then $d=b^2-a^2=(b+a)(b-a)$. But any given integer $d$ has only finitely many factorizations, $d=rs$ (with $r$ and $s$ of the same parity). Setting $b+a=r$ and $b-a=s$ and solving for $a=(r-s)/2$ and $b=(r+s)/2$, we conclude there are only finitely many possibilities for $a^2$ and $b^2$.

$\endgroup$
1
  • 2
    $\begingroup$ Brilliant! This is a very clever apporach indeed. $\endgroup$ Commented Feb 22, 2017 at 19:42
12
$\begingroup$

You way looks fine to me, here's another way:

Suppose $d$ is the common difference in some arithmetic progression. Let $p$ be any prime other than $2$ that doesn't divide $d$. It's not hard to show that then the arithmetic progression hits every residue class mod $p$, but only $\frac{p+1}{2}$ of them are quadratic residues so they can't all be squares.

$\endgroup$
7
  • 1
    $\begingroup$ Can you actually show that it gives every remainder mod $p$? I haven't learned modular arithmetic yet. (Not as well I want to at least) $\endgroup$ Commented Feb 22, 2017 at 18:49
  • 2
    $\begingroup$ If it doesn't hit all the residue classes mod $p$ then of the first $p$ terms two of them say $A_i$ and $A_j$ must be the same class mod $p$ by the pigeonhole principle. But that means $p$ divides $ (A_j-A_i)= d(j-i)$, but $p$ doesn't divide $d$ or $(j-i)$ as $i,j<p$ which contradicts the fact that $p$ is prime. $\endgroup$ Commented Feb 22, 2017 at 19:00
  • 4
    $\begingroup$ I don't like this proof, because it is more complicated than the obvious proof given by the OP. (Yes, the OP's proof is longer, but it can be made shorter: the difference between successive squares grows without bound, but the difference between successive elements of an AP is constant.) $\endgroup$ Commented Feb 22, 2017 at 22:38
  • 1
    $\begingroup$ @jwg - If my answer and OP's solution had both been posted as answers to the same question I'd probably vote for his over mine, my point was that OP specifically asked for other approaches so I think posting this approach was appropriate. I hardly agree that reducing things modulo a prime is ugly or excessively complex though. Also, you seem to think OP's proof gets at the "real" reason why this result is true while mine does not, to that I'd suggest you try to prove the same result for perfect squares in $\mathbb{Z}[\sqrt{2}]$. $\endgroup$ Commented Feb 24, 2017 at 15:48
  • 1
    $\begingroup$ That's a lot of bitching for a single downvote. $\endgroup$ Commented Feb 24, 2017 at 18:44
7
$\begingroup$

Yes, this is a very good way to prove it. It generalizes readily to higher powers and many other sequences. Other methods can give tighter bounds but may require more number theory, for instance:

  • The number of terms in an arithmetic progression that are $\le n$ is $\Theta(n)$ with constants depending on the specific progression, but the number of squares up to $n$ is only $O(\sqrt{n})$.

  • Pick $p$ to be the smallest odd prime that doesn't divide $d$ (this is at most $O(\log d)$ in size). Then one of the first $p$ terms will be a quadratic non-residue mod $p$.

  • Using an infinite descent argument, it can be shown that there is no AP of length 4 in the set of perfect squares. This was first observed by Fermat and can be shown by more modern methods, but the folklore of the elementary proof seems to have a bit of a history (see http://www.mathpages.com/home/kmath044/kmath044.htm as well as https://arxiv.org/abs/0712.3850).

$\endgroup$
2
  • 3
    $\begingroup$ (+1) I would just add a link : mathpages.com/home/kmath044/kmath044.htm $\endgroup$ Commented Feb 22, 2017 at 19:13
  • 1
    $\begingroup$ @JackD'Aurizio Thanks for the link! I was on mobile and it wasn't convenient to include this in my original post. $\endgroup$ Commented Feb 22, 2017 at 19:50
5
$\begingroup$

I believe it can also be proven by noting that the common difference between any consecutive squares is unbounded.

For any common difference $d$, there exist two consecutive squares whose difference is greater than $100d$. There must be at least one term in the arithmetic progression which falls between these two squares, and as such, is not a square.

$\endgroup$
2
  • 4
    $\begingroup$ Isn't this the same proof as OP's but with some details abstracted away? $\endgroup$ Commented Feb 23, 2017 at 9:24
  • 2
    $\begingroup$ Yes, pretty much. I feel like it is way easier to understand though. $\endgroup$ Commented Feb 23, 2017 at 21:04

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.