1
$\begingroup$

Prove that there are arbitrarily long sequences of consecutive integers, none of which can be written as the sum of two perfect squares.

First few numbers are $3,6,7,11,12,14,15,19,21,22,23,24,27,28,30,31,33,35,38,39, \cdots$

Sums of squares can only be of the form $4k$, $4k+1$ and $4k+2$. So can we use this idea to prove the proposition?

I didn't find a logical sequence. Can anyone provide some hints to proceed with this?

|cite|improve this question
$\endgroup$
8
$\begingroup$

A number is a sum of two squares if and only if all primes $3$ mod $4$ appear only to even powers in its prime factorisation.

So we want arbitrarily long sequences of consecutive integers such that for each $n$ in the sequence, some prime $p \equiv 3 \pmod{4}$ appears to an odd power in the prime factorisation of $n$.

There are infinitely many primes $3$ mod $4$; say the $n$th is $p_n$.

Then we can guarantee that a number is divisible by $p_n$ but not $p_n^2$ by insisting that it be of the form $m$ where $m \equiv p_n \pmod{p_n^2}$.

By the Chinese remainder theorem, we can find $a$ such that $a+1 \equiv p_1 \pmod{p_1^2}$, $a+2 \equiv p_2 \pmod{p_2^2}$, and so on up to $a+k \equiv p_k \pmod{p_k^2}$. This is a sequence of $k$ consecutive integers, none of which is a sum of two squares.

For example, if $k=5$, we wish to find $a$ such that $$a+1 \equiv 3 \pmod{9} \\ a+2 \equiv 7 \pmod{49} \\ a+3 \equiv 11 \pmod{121} \\ a+4 \equiv 19 \pmod{361} \\ a+5 \equiv 23 \pmod{529}$$

The smallest such $a$ is $1789983137$ (and it is unique with this property modulo $10190296809$). Therefore $$ 1789983138,1789983139,1789983140,1789983141, 1789983142$$ is such a sequence. I emphasise that this is only one working sequence; in fact the smallest is $75, 76, 77, 78, 79$.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Could you please include an example for $k=5$? $\endgroup$ – TheRandomGuy Mar 25 '16 at 13:42
  • $\begingroup$ @Dhruv Done. I doubt it'll be very helpful though :P $\endgroup$ – Patrick Stevens Mar 25 '16 at 13:50
  • 1
    $\begingroup$ You don't really need $a+4$ congruent with 19 mod 361. It's already congruent with 6 mod 9. Drop that condition, replace 23 with 19 (and swap the squares of those two numbers) for $a+5$, and see how much smaller the numbers get. $\endgroup$ – Oscar Lanzi Mar 31 '16 at 0:02
  • $\begingroup$ @OscarLanzi That yields an example with $a=24907978$. Well spotted. $\endgroup$ – Patrick Stevens Mar 31 '16 at 7:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.