Let $ b_1<b_2<b_3<\dots $ be the sequence of all natural numbers which are sum of squares of two natural numbers. Prove that there exists infinite natural numbers like $m$ which $b_{m+1}-b_m=2015$ .
Problem
Source: Iran TST 2015, exam 1, day 1 problem 3
Tags: number theory
18.05.2015 11:22
Let $p_1,p_2,...,p_{2014}$ be distinct prime numbers such that $p_i\equiv 3(\mathrm{mod}\ 4)$. By CRT, the system $x\equiv 2(\mathrm{mod}\ 8),\ x\equiv p_i-i(\mathrm{mod}\ p_i^2)\ \forall i\in \{1,2,..,2014\}$ has an infinite set $S$ of solutions. Then for any $x\in S$, $x=2(4k+1),\ x+2015=4l+1$, hence $x$ and $x+2015$ can be written as the sum of two squares, while $x+i$ (with $1\le i\le 2014)$ is divisible by $p_i$ but not by $p_i^2$ hence it cannot be written as the sum of two squares. Thereby, there is $m$ such that $b_m=x$, $b_{m+1}=x+2015$, i.e. $b_{m+1}-b_m=2015$, whence the conclusion.
18.05.2015 12:12
Quote: Then for any $x\in S$, $x=2(4k+1),\ x+2015=4l+1$, hence $x$ and $x+2015$ can be sum of two squares Why?It is not enough that number is of the form $4k+1$ or $2*(4l+1)$,it may exist some prime $q$ of the form $4m+3$ such that $q$ divides $4k+1$ and $q^2$ doesn't divide $4k+1$.I don't see how did you proved that.
18.05.2015 15:11
Note that if $2b - a = 1005$ then $(a-1)^2 + (b+2)^2 - a^2 - b^2 = 1005$ so it suffices to show that $a^2 + b^2 + 1 , ..., a^2 + b^2 + 2014$ cannot be represented as sum of two squares. We can then use a similar idea as Aiscrim to get $a^2 + b^2 + i \equiv p_i \pmod { {p_i}^2} $ for some primes $p_1,p_2,...,p_{2014}$ and we are done. This is equivalent to solving $x^2 \equiv mp_i - n - i \pmod {{p_i}^2}$ for some natural $m,n$ for all $i$. We can take a solution of $x^2 \equiv -n - i \pmod {p_i}$ of which infinitely many such primes $p_i$ exist and then lifting it by replacing $x$ with $x+kp$ and varying $k$.
18.05.2015 15:13
Let $x$ be defined by CRT through $x\equiv p_i-i(\mathrm{mod}\ p_i^2)\ \forall i\in \{1,2,..,2014\}$ with $p_i\equiv 3(\mathrm{mod}\ 4)$,as in Aiscrim's solution.If we find an infinitude of $a$'s so that there exists $k$ for which $a^2+1007^2=x+k\prod p_i^2$.Label this number $y$.By aiscrim's argument we have that $y+i$ (with $1\le i\le 2014)$ cannot be written as sum of 2 squares,whereas $y=a^2+1007^2,y+2015=a^2+1008^2$ and we're done.Obviously,if we find only one such $a$,by taking $a+j\prod p_i^2$ for every $j$ we get an infinitude of satisfactory $a$'s,Q.E.D. Now it only remains to find such an $a$.Notice that we can still choose our $p_i$'s,as long as they are distinct and congruent to 3 mod 4. Suppose that $1007^2+i$ would be a residue modulo every prime $\equiv 3(\mathrm{mod}\ 4)$ bigger than some $N$;then let $m$ be the squarefree component of $1007^2+i$ and let its prime decomposition be $m=\prod_1^s q_i$;we would need $m$ to be a residue modulo every prime described above.$m$ obviously cannot be 1.If $m$ is $2$,then we have an easily provable contradiction,so assume there exists an odd prime factor of $m$,let it be $q_s$,and pick a non-quadratic residue of it $a$.By CRT there exists a number $l$ so that $l\equiv 3(\mathrm{mod}\ 4)$,$l\equiv a(\mathrm{mod}\ q_s)$ and $l\equiv 1(\mathrm{mod}\ q_i) \forall i\in \{1,2,..,s-1\}$.By Dirichlet's Theorem,since $l$ and $4m$ are coprime,the set $\{l+4jm|j \in \mathbb{N} \}$ has an infinite amount of primes,and thus an infinite amount of primes bigger than $N$;let one of them be $M$.But now by properties of Legendre's Symbol we obtain that $m$ is a nonquadratic residue mod $M$,contradiction with our assumption since $M\equiv 3(\mathrm{mod}\ 4)$. So there must exist,$\forall i\in \{1,2,..,2014\}$,an infinite number of primes $p$ for which $1007^2+i$ is a nonresidue mod $p$,since otherwise there would exist an $N$ so that for every prime $\equiv 3(\mathrm{mod}\ 4)$,$1007^2+i$ is a residue,contradiction with the above. Now we can easily pick distinct $p_i\equiv 3(\mathrm{mod}\ 4)$ so that $1007^2+i$ is a nonresidue mod $p_i$,$\forall i\in \{1,2,..,2014\}$;but then we have that $-1007^2-i$ IS a quadratic residue mod $p_i$. Now,for any $i\in \{1,2,..,2014\}$,we can pick $a_i$ so that $a_i^2\equiv -1007^2-i\equiv -1007^2-x(\mathrm{mod}\ p_i)$.One of the numbers $a_i,a_i+p_i,...,a_i+p_i(p_i-1)$,we call him $b_i$,will then satisfy $b_i^2 \equiv -1007^2-x(\mathrm{mod}\ p_i^2)$.Now we choose $a$ by $CRT$ as $a \equiv b_i(\mathrm{mod}\ p_i^2)$;it will obviously satisfy the relations $a^2 \equiv -1007^2-x(\mathrm{mod}\ p_i^2)$,thus it satisfies $a^2 \equiv -1007^2-x(\mathrm{mod}\ \prod p_i^2)$,which is exactly $a^2+1007^2=x+k\prod p_i^2$ written in modulo terms.Thus we have found our $a$,and thus the solution is complete.
10.02.2016 16:01
Fix some primes $p_1,...,p_{2014}$ such that they are all distinct (and greater than $1008^2$) and $p_i\equiv 3(\mathrm{mod}\ 8)$ and $\left ( \dfrac{1007^2+i}{p_i} \right )=-1$. By CRT, the system $x+i\equiv p_i(\mathrm{mod}\ p_i^2)$ for $1\le i\le 2014$ has a solution $x\equiv k (\mathrm{mod}\ p_1^2p_2^2....p_k^2)\ \ (*)$. Obviously, any number satisfying this system has the property that $x+i$ cannot be written as the sum of two squares for any $1\le i\le 2014$. Note that $$\left ( \dfrac{k-1007^2}{p_i} \right )=\left ( \dfrac{-i-1007^2}{p_i} \right )=-\left ( \dfrac{1007^2+i}{p_i} \right )=1$$so there exists $x_i$ such that $x_i^2\equiv k-1007^2(\mathrm{mod}\ p_i)$. As $p_i$ does not divide $k-1007^2$ ($p_i>1008^2>1007^2+i$), we have that $p_i$ does not divide $x_i$ either. Taking $t\equiv -\dfrac{x_i-(k-1007^2)}{p}\cdot (2x_i)^{-1} (\mathrm{mod}\ p)$, we have that $p_i^2$ divides $(x_i+pt)^2-(k-1007^2)$. Denote $t_i=x_i+pt$. By CRT, we can find infinitely many positive integers $a$ such that $a\equiv t_i (\mathrm{mod}\ p_i^2)$. By the way we chose $a$, we have that $$p_1^2p_2^2...p_{2014}^2|a^2-(k-1007^2)\Leftrightarrow a^2-(k-1007^2)=\beta_ap_1^2p_2^2...p_{2014}^2$$ We are now done: take $n=\beta_ap_1^2p_2^2...p_{2014}^2+k$. As $n$ satisfies the system $(*)$, the numbers $n+1,...,n+2014$ cannot be written as the sum of two squares. In the same time $n=a^2+1007^2$ and $n+2015=a^2+1008^2$. By making $a$ very big, $n$ can become arbitrarily large, whence the conclusion.
21.03.2017 19:11
I'll work with numbers $5(y^2+202^2),5(y^2+201^2)$ for $y$ to be choosen later.Firstly note that they are both sum of two squares as $5=2^2+1^2$ and the set of the numbers being sum of two squares is closed under $\cdot$ and hence the desired.On the other hand their difference is $5(202-201)(201+202)=2015$.Now pick some 2014 prime numbers so that $p_i\equiv 3 \pmod 4$ where $p_i$ is much larger that $5\cdot 202^2$ and $\left(\tfrac{(5\cdot 201^2+1)\cdot 5^{-1}}{p_i}\right)=-1$.Now select $y$ as the solution to the : $$y^2\equiv \frac{p_i-1}{5}-201^2 \pmod {p_i^2} \forall i\leq 2014$$Notice that as $y^2=-\tfrac{(5\cdot 201^2+1)}{5}$ has a solution in $\mathbb{Z}_{p_i}$ by Hensel's it has one in $Z_{p_i^2}$ and and hence we can pick by $y$ by CRT so that it satisfies previous conditions.Now let's show that in $(5(y^2+202^2),5(y^2+201^2))$ no number is the sum of two squares.This however follows immidiately after the construction as for $\forall a\in (5(y^2+202^2),5(y^2+201^2))$ we have $a\equiv p_i \pmod {p_i^2}$ for some $p_i$ a contradiction as it's well known that $v_{p_i}$ is either zero or even.So our constructed $y$ satisfies the conditions.Now just pick another 2014 primes each $\equiv 3\pmod 4$ to construct how many $y$ we want and hence there are infinitely many of them.$\blacksquare$
09.11.2019 22:30
I found a solution which not related to Dirichlet's Theorem or some unfamiliar quadratic-residue properties in my high school days but was too lazy to write down. Recently, one of my students has asked me about the problem in this post so I'd like to share it here. First, we have three lemmas. Lemma: A positive integer $n$ can be written as a sum of two squares if and only if $v_p(n)$ is even for all prime number $p$ of the form $4k+3$. Lemma: Let $p$ be an odd prime number and $n$ be a integer that $p$ does not divide $n$. Then exists two integer $a,b$ that $$a^2+b^2 \equiv n \pmod {p^2}$$Lemma: Let $a,b,c$ be positive integers. Then exist a integer $k$ that $(a+kb,c)=1$ if and only if $(a,b,c)=1$. The first one is quite well-known. The second one can be approached by many ways. We can prove it for modulo $p$, then lift to $p^2$ by the idea of Hensel's lemma. In the last one, we can decompose the number $c$ to prime divisors, choose $k$ for individual prime divisor of $c$, and use CRT to choose a common $k$. Back to the problem. We will prove this: for a positive integer $n$, there is a positive number $x$ that $x,x+n$ are both sum of two squares, but none of $x+1,\ldots,x+n-1$ is. Note that there are infinitely many primes of the form $4k+3$, so we can choose $n-1$ distinct prime numbers $p_i$ of this form and larger than $n$ (we use this condition later). Let $X = (\prod_i^{n-1} p_i)^2$. Note that $p_i$ does not divide $p_i-i$ since $p_i > n > i$ (we need $p_i>n$ here), so by the second lemma, we can choose two integers $a,b$ that $p_i^2 | a^2+b^2+i-p_i$. Now we will choose $4$ number $c,d,A,B$ satisfy $(A,B)=1$ and this equation $$(a+cX)^2+(b+dX)^2 +n = (a+cX+A)^2+(b+dX+b)^2$$This equivalent to $$\dfrac{n+a^2+b^2-(a+A)^2-(b+B)^2}{2X} = Ac+Bd ~~~ (*)$$ Let discuss why we come to this weird equation. If we take $x=(a+cX)^2+(b+dX)^2$, then $v_{p_i}(x+i)=1$ since $a+cX$ and $b+dX$ remains the same as $a$ and $b$ modulo $X$, so $x+i$ can not be sum of two squares. Moreover, $x+n = (a+cX+A)^2+(b+dX+b)^2$ is sum of two square. Then the number $x$ is what we need! Back to the equation $(*)$. First, we will choose $A,B$ modulo $2X$ that the fraction in the left of $(*)$ be integer. To handle the number $X$, once again we use the second lemma for every divisor $p_i^2$ of $X$ (note that $n+a^2+b^2 \equiv n-i \not\equiv 0 \pmod {p_i}$). For the number $2$, we can choose $A,B$ satisfy the condition and $A-B$ is odd. Then using CRT, we can choose common $A,B$ modulo $2X$ for all these condition. You will wonder why we need $A-B$ is odd. Now we take $A$ to $A+k2X$ to get $(A+k2X,B)=1$, and also remain $A,B$ modulo $2X$. Since we have the third lemma, we have to show that $(A,B,2X)=1$ (we need $X-Y$ odd and also $p_i>n$ here). It is quite obviously so we omit it. So now we have $A,B$ satisfy the left side of the equation $(*)$ is an integer and $(A,B)=1$. To get $c,d$, recall a familiar theorem which state that if $(A,B)=1$, there are integers $u,v$ that $uA+vB=1$. Now take $c,d$ equal to $u,v$ times the number on the left side to finish the proof. The infinitely-condition can be done by taking $p_i$ arbitrary large. The proof above do not show how large of the number $x$, but if we take $p_1$ to be sufficiently large, since $p_1$ divides $x+1$, then $x$ must be "large" as $p_1$. P/s: I’m working on improving my English, so please excuse any mistakes.
26.07.2020 12:10
We prove the statement for general odd $2k+1$ . We prove that there exist infinitely many $N$ such that none of the numbers $\{N^2+k^2+j\}_{j=1}^{2k}$ are representable as the sum of two perfect squares . The main idea of the proof is that we will construct primes $\{p_j\}_{j=1}^{2k}$ such that $p_j \equiv 3 \pmod 4 $ and $\nu_{p_j}(N^2+k^2+j)=1$ . This obviously finishes . We will use two well known lemmas : Lemma 1 : Given a positive integer $a$ which is not a perfect square , there exist infinitely many primes $p \equiv 3 \pmod 4$ such that $\left( \frac ap \right)=-1$ . We omit the proof as it is quite classical and well known . Lemma 2 : Given a quadratic residue $r$ modulo $p$ , there exists a positive integer $x$ with $0<x<2p$ with $p \nmid x$ such that the following congruences hold: $$ x^2 \equiv r \pmod p \quad x^2 \neq r \pmod {p^2}$$ Proof : Simply note that $x^2$ and $(x+p)^2$ are congruent to the same quadratic residue modulo $p$ . However : $$ (x+p)^2-x^2 = 2px + p^2 \neq 0 \pmod {p^2}$$Hence atleast one of $x$ and $x+p$ is a solution. $\blacksquare$ Now we return to the problem at hand . Pick $2k$ primes $p_1,p_2, \dots p_{2k}$ such that all of them are of the form $3 \pmod 4$ and $$ \left ( \frac {k^2+j}{p_j} \right) =-1 \quad \forall 1\leq j \leq 2k$$ Allow $k^2+j \equiv -r_j \pmod {p_j}$ . Note that $r_j$ is a quadratic residue modulo $p_j$ . By the lemma 2 , we can find a $k_j$ with $(k_j,p_j)=1$ and $0<k_j<2p_j$ , for all $1\leq j\leq 2k$ such that : $$ {k_j}^2 \equiv r_j \pmod {p_j} \quad {k_j}^2 \neq r_j \pmod {p_j^2}$$ Now we let $$N= k_j \pmod {p_j^2} \quad \forall 1\leq j \leq 2k $$ Hence we observe that each of the numbers in the sequence $\{N^2+k^2+j\}_{j=1}^{2k}$ are fully divisible by a odd exponent of a $3 \pmod 4$ prime and hence can never be represented as the sum of two perfect squares . We finish by noting $$2k+1=(N^2+(k+1)^2)-(N^2+k^2)$$ We are done . $\blacksquare$
12.10.2020 02:00
Solved with nukelauncher. Say a number is fit if it is the sum of two squares, and unfit otherwise. Observe that if \(n\) is divisible by a prime \(p\equiv3\pmod4\) but not \(p^2\), then \(n\) is unfit. Note that for all integers \(x\), the numbers \(x^2+1007^2\) and \(x^2+1008^2\) are fit and differ by 2015. It will suffice to show there are infinitely many \(x\) such that the numbers \(x^2+1007^2+1\), \(x^2+1007^2+2\), \ldots, \(x^2+1007^2+2014\) are unfit. Lemma: [Well-known QR] For every \(i\) that is not a perfect square, there is a prime \(p\equiv3\pmod4\) with \(p-i\) a quadratic residue modulo \(p^2\). Proof. By Hensel's lemma, it is sufficient to show there is a \(p\equiv3\pmod4\) prime with \(-i\) a quadratic residue modulo \(p\); that is, \(i\) not a quadratic residue modulo \(p\). Let \(i=q_1q_2\cdots q_k\cdot(\text{square})\), where \(q_1\), \ldots, \(q_k\) are distinct. Then \[\left(\frac ip\right)=\prod_{i=1}^k\left(\frac{q_i}p\right)=\pm\prod_{i=1}^k\left(\frac p{q_i}\right),\]It is obvious by Dirichlet theorem we can find \(p\) with the above expression equal to \(-1\). \(\blacksquare\) Now for each \(i=1,\ldots,2014\), let \(p_i\) be a prime with \(p_i-(i+1007^2)\) a quadratic residue modulo \(p_i^2\) by the lemma. Then take \(P=p_1p_2\cdots p_{2014}\) and \(c\) a constant with \[c^2\equiv p_i-(i+1007^2)\pmod{p_i^2}\quad\text{for all }i=1,\ldots,2014.\]It follows that for all \(j\), the number \(x=P^2j+c\) has the property that \(x^2+1007^2+i\equiv p_i\pmod{p_i^2}\) for \(i=1,\ldots,2014\); that is, each \(x^2+1007^2+i\) is divisible by a \(3\pmod4\) prime but not its square, so it is unfit. There are infinitely many such \(x\) of the form \(P^2j+c\), so this completes the proof.
28.02.2021 04:27
Some motivation: It's easy to force 2014 consecutive numbers to not be sum of two squares, but it's not so easy to force two numbers to be sum of two squares. So we force the sum of two numbers to be sum of two squares via algebraic methods, and force the 2014 consecutive numbers to not be sum of two squares in a similar way. When I experimented with $(a+1)^2+(a-1)^2=2a^2+2$, I am inspired to use $2a=b+1005, x=a^2+b^2, x+2015=(a+2)^2+(b-1)^2$. Then we can see $x+k=a^2+(2a-1005)^2+k=5a^2-4020a+1005^2+k=5(a-402)^2+k+C$ for some constant $C$. We force $5(a-402)^2+k+C\equiv p_k(\bmod\; p_k^2)$ for $1\le k\le 2014, p_k\equiv -1(\bmod\; 4)$. This is equivalent to $5(a-402)^2\equiv p_k-k-C(\bmod\; p_k^2)$. This is not hard to just do; pick $p_k>500,$ first find $5(a-402)^2\equiv -(k+C) (\bmod\; p_k)$, which is viable through dirichlet and quadratic reciprocity. Then, for that $a$, we consider $5(a-402)^2, 5(a+p-402)^2,\cdots, 5(a+(p-1)p-402)^2$. It's not hard to verify they are distinct mod $p^2$ but same mod $p$, so we can pin down $a$ mod $p_k^2$, then finish with Chinese Remainder Theorem.
05.09.2021 17:14
Note that if $2b - a = 1005$ then $(a-1)^2 + (b+2)^2 - a^2 - b^2 = 2015$ so it suffices to show that $a^2 + b^2 + 1 , ..., a^2 + b^2 + 2014$ cannot be represented as sum of two squares.
,choose \begin{align*} a^2 \equiv -b^2-1 \pmod {p_1^2} \\ a^2 \equiv -b^2-2 \pmod {p_2^2} \\ . \\ . \\ . \\ . \\ a^2 \equiv -b^2-2014 \pmod {{p_{2014}^2} } \end{align*}and it's easy to guarantee that the congruencies have solutions so we are done$\blacksquare$ Edit:350th post!!!!!!!!