Sequence of numbers in form of a^2+b^2

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Sequence of numbers in form of a^2+b^2

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: Iran TST 2015, exam 1, day 1 problem 3

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

97 posts

#1 h May 11, 2015, 2:14 PM • 5 Y

Y by Dadgarnia, Hc417, adityaguharoy, Adventure10, Mango247

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$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

409 posts

#4 h May 18, 2015, 8:22 AM • 2 Y

Y by Adventure10, Mango247

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

314 posts

#5 h May 18, 2015, 9:12 AM • 1 Y

Y by Adventure10

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.

This post has been edited 1 time. Last edited by junioragd, May 18, 2015, 9:13 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

615 posts

#6 h May 18, 2015, 12:11 PM • 3 Y

Y by andreiromania, doxuanlong15052000, Adventure10

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$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

52 posts

#7 h May 18, 2015, 12:13 PM • 2 Y

Y by Adventure10, Mango247

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

409 posts

#9 h Feb 10, 2016, 2:01 PM • 5 Y

Y by biomathematics, SidVicious, nguyenhaan2209, Adventure10, Mango247

Lemma: For any number $1\le i\le 2014$ , we can find an infinite number of primes $p$ such that $p\equiv 3(\mathrm{mod}\ 8)$ and $\left ( \dfrac{1007^2+i}{p} \right )=-1$ Proof.

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1246 posts

#10 h Mar 21, 2017, 4:11 PM • 2 Y

Y by Adventure10, Mango247

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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

53 posts

#11 h Nov 9, 2019, 7:30 PM • 2 Y

Y by pavel kozlov, Adventure10

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.

This post has been edited 8 times. Last edited by MaySayToc124, Oct 29, 2020, 2:04 PM
Reason: typo

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

558 posts

#12 h Jul 26, 2020, 9:10 AM • 2 Y

Y by AlastorMoody, pavel kozlov

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$

This post has been edited 1 time. Last edited by Aryan-23, Jul 26, 2020, 9:23 AM
Reason: Typo

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1740 posts

#13 h Oct 11, 2020, 11:00 PM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1301 posts

#14 h Feb 28, 2021, 1:27 AM

Y by

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.

This post has been edited 2 times. Last edited by CANBANKAN, Feb 28, 2021, 8:25 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

478 posts

#15 h Sep 5, 2021, 2:14 PM

Y by

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.
By Generalized Chestnut Ramification Theorem,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!!!!!!!! :pilot:

:pilot:

This post has been edited 8 times. Last edited by Sprites, Sep 5, 2021, 3:18 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

203 posts

#17 h Apr 3, 2025, 6:36 AM

Y by

Pretty standard. This is the main claim.

Claim: If $x \in \mathbb{N}$ such that it is not a perfect square then there exists infinitely many primes $p \equiv 3 \pmod 4$ such that $x$ is NQR $\bmod p$ .
Proof: If we remove the $3 \pmod 4$ condition on $p$ , then we proceed the normal way, that is using QR law and manually choosing what we want $\left(\frac{p}q \right)$ to be where $\nu_q(x)$ is odd (and $q$ is odd); which only depends on $q$ .

So see that when we take the CRT at the end, for the odd $q$ we are fine but the problem we will have is choosing $\left(\frac 2p \right)$ but see that if we want it to be QR then choose $p \equiv 7 \pmod 8$ and $p \equiv 3 \pmod 8$ otherwise. Now do a big aah Dirichlet at the end. $\square$

Let $b=B^2+1007^2$ and $b+2015=B^2+1008^2$ .

Let $p_i \equiv 3 \pmod 4$ be large primes (from $1$ to $2014$ ) such that $\left(\frac{1007^2+i}{p_i} \right)=-1$ by our above lemma; which is possible as $1007^2+2014<1008^2$ .

Hence see that we need $B$ such that $f_i(B)=B^2+1007^2+i \equiv p_i \pmod {p_i^2}$ for all $1 \le i \le 2014$ which is true by Hensel's lemma (see that $f_i(B)$ has a solution $\bmod p_i$ and doesn't satisfy $f_i'(B) \equiv 0$ as $p_i$ is large) and CRT at the end.

And so by Fermat's Christmas theorem, we get that $b+1$ , $\dots$ , $b+2014$ can not be written as sum of $2$ squares.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

705 posts

#18 h Apr 10, 2025, 6:36 PM • 1 Y

Y by MS_asdfgzxcvb

Lemma: We can find infinitely many primes $\equiv 3(mod \ 4)$ where a non-perfect square $a\in \mathbb{Z}^+$ is not a quadratic residue.
Proof: We will use Chinese Remainder Theorem and Drichlet. Let $q_1\dots q_k$ be the squarefree part of $a$ . Pick $p\equiv 1(mod \ q_1\dots q_{k-1})$ and $p\equiv 7(mod \ 8)$ . If $\nu_2(a)$ is odd, note that $(\frac{2a}{p})=(\frac{a}{p})$ hence assume that $q_i'$ s are odd. Then, $(\frac{a}{p})=(\frac{q_1}{p})\dots (\frac{q_k}{p})=(-1)^k(\frac{p}{q_1})\dots (\frac{p}{q_k})=(-1)^k(\frac{p}{q_k})$ . If $k$ is even, then pick $p$ non-quadratic residue mod $q_k$ and if $k$ is odd, pick $p\equiv 1(mod \ q_k)$ .

Let $1007^2=\ell$ , note that none of $\ell+1,\dots, \ell+2014$ is a perfect square and let $2025!\ell^{2024}<p_1<\dots <p_{2014}$ be $2014$ primes $\equiv 7(mod \ 8)$ such that $(\frac{-\ell-i}{p_i})=-(\frac{\ell+i}{p_i})=1$ . Let $m_i^2\equiv -l-i(mod \ p_i)$ such that $p_i^2\not | m_i^2+\ell+i$ which can be provided since if $p_i^2|m_i^2+\ell+i$ , then $p_i^2\not | (p_i-m)^2+\ell+i$ . We have
$m_i^2+\ell+i\equiv p_it_i(mod \ p_i^2)$ where $(p_i,t_i)=1$ hence $m_i^2\equiv t_ip_i-\ell-i(mod \ p_i^2)$ for all $1\leq i\leq 2014$ . Pick $k\equiv m_i(mod \ p_i^2)$ which exists by Chinese Remainder Theorem. This implies $k^2\equiv m_i^2\equiv t_ip_i-\ell-i(mod \ p_i^2)$ thus, $\nu_{p_i}(k^2+\ell+i)=1$ and this gives that none of $k^2+\ell+1,\dots, k^2+\ell+2014$ can be written as sum of two squares and $k^2+1007^2,k^2+1007^2+2015=k^2+1008^2$ can be written as desired. $\blacksquare$

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a