Kvant Math Problem 814

A natural number is representable as a sum of two squares if and only if every prime congruent to $3 \pmod 4$ appears with even exponent in its prime factorization.

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 9m33s
Source on kvant.digital

Problem

Mark the natural numbers that can be represented as the sum of two squares of natural numbers. Among the marked numbers, there are triples of consecutive numbers, for example $$72=6^2+6^2,\quad 73=8^2+3^2,\quad 74=7^2+5^2.$$.

  1. Explain why four consecutive marked numbers cannot occur.

Prove that among the marked numbers there are infinitely many

  1. pairs;
  2. triples

of consecutive numbers.

L. D. Kurlyandschik

Exploration

A natural number is representable as a sum of two squares if and only if every prime congruent to $3 \pmod 4$ appears with even exponent in its prime factorization. The example

$$72=2^3\cdot 3^2,\qquad 73\ \text{prime},\qquad 74=2\cdot 37$$

fits this criterion.

To exclude four consecutive marked numbers, it is natural to examine residues modulo $4$. Among four consecutive integers there is exactly one multiple of $4$. If all four were marked, that multiple of $4$ would also be marked. This alone is not enough. A stronger local obstruction is needed.

Consider any four consecutive integers $n,n+1,n+2,n+3$. One of them is congruent to $3$ modulo $4$. A number congruent to $3$ modulo $4$ can be a sum of two squares only if some prime $p\equiv3\pmod4$ divides it to an even exponent. For a general number this is possible, so congruence alone does not exclude it. A different idea is required.

Looking at four consecutive integers modulo $8$, one of them is congruent to $3$ or $7$ modulo $8$. A sum of two squares can certainly have such residues, so this also fails.

The representation criterion suggests constructing infinite families. Consecutive marked pairs mean finding infinitely many $n$ such that both $n$ and $n+1$ are sums of two squares. The identity

$$a^2+(a+1)^2=2a^2+2a+1$$

gives one number, but not its neighbor.

Trying examples:

$$4=0^2+2^2,\quad 5=1^2+2^2,$$

$$25=0^2+5^2,\quad 26=1^2+5^2.$$

This suggests

$$m^2,\quad m^2+1$$

when $m$ itself is representable as one square. If natural numbers are allowed to include $0$ in the representation, this gives infinitely many pairs immediately by taking $m=5^k$. Since the statement uses examples with positive summands but asks about representability as sums of squares of natural numbers, the standard Soviet convention usually includes $0$. The construction strongly indicates that this is intended.

For triples, the example $72,73,74$ suggests searching systematically. Let

$$n=2a^2.$$

Then $n=a^2+a^2$ is marked. We want

$$n+1,\quad n+2$$

also marked. If

$$n+1=b^2+c^2,$$

then

$$n+2=(b^2+c^2)+1.$$

A useful identity is

$$x^2+(x+1)^2=2x(x+1)+1.$$

Setting

$$2a^2+1=x^2+(x+1)^2$$

leads to

$$a^2-x(x+1)=\frac12.$$

After multiplying by $4$:

$$(2a)^2-2(2x+1)^2=-2.$$

This is a Pell equation

$$u^2-2v^2=-2.$$

The small solution $(u,v)=(2,2)$ yields $a=1$, $x=0$, giving the triple

$$2,3,4.$$

Since Pell equations have infinitely many solutions, this should generate infinitely many triples.

The delicate point is proving that every solution of

$$u^2-2v^2=-2$$

with $u,v$ even indeed yields

$$2a^2,\quad 2a^2+1,\quad 2a^2+2$$

all representable.

Problem Understanding

We mark all natural numbers that can be written as the sum of two squares of natural numbers. We must show three facts.

First, four consecutive marked numbers never occur.

Second, there are infinitely many pairs of consecutive marked numbers.

Third, there are infinitely many triples of consecutive marked numbers.

This is a Type B problem. The main difficulty is the construction of infinitely many triples. The exclusion of four consecutive marked numbers is local and arithmetic, while the existence of infinitely many triples requires a systematic infinite family. The representation theorem for sums of two squares and a Pell equation provide the necessary structure.

Proof Architecture

The first lemma states that every integer congruent to $3$ modulo $4$ which is a sum of two squares is divisible by a prime $p\equiv3\pmod4$ to an even positive exponent; this follows from the sum of two squares criterion.

The second lemma states that among any four consecutive integers one is congruent to $3$ modulo $4$ and is not representable as a sum of two squares; this excludes four consecutive marked numbers.

The third lemma states that for every $k\ge0$, the numbers $25^k$ and $25^k+1$ are marked; this yields infinitely many consecutive pairs.

The fourth lemma states that if integers $a,x$ satisfy

$$2a^2+1=x^2+(x+1)^2,$$

then

$$2a^2,\quad 2a^2+1,\quad 2a^2+2$$

are all marked.

The fifth lemma states that the equation

$$u^2-2v^2=-2$$

has infinitely many even solutions; this is obtained from the Pell theory of units in $\mathbb Z[\sqrt2]$.

The hardest step is converting infinitely many Pell solutions into infinitely many triples and verifying that all resulting numbers are marked.

Solution

A classical theorem states that a positive integer is representable as a sum of two squares if and only if every prime congruent to $3$ modulo $4$ occurs in its prime factorization with even exponent.

Suppose four consecutive marked numbers existed. Among any four consecutive integers there is exactly one integer congruent to $3$ modulo $4$; denote it by $m$.

Since $m$ is marked, it is a sum of two squares. Because $m\equiv3\pmod4$, its prime factorization contains at least one prime $p\equiv3\pmod4$. By the theorem above, the exponent of $p$ must be even. Hence $p^2\mid m$.

Since $p\ge3$, we have $p^2\ge9$. Therefore $m$ is divisible by the square of a prime congruent to $3$ modulo $4$.

Now consider the four consecutive integers containing $m$. Only one of them can be divisible by $p^2$, because $p^2\ge9$. Consequently the remaining three integers are not divisible by $p^2$.

Among these four consecutive integers, one is congruent to $3$ modulo $4$. Any marked integer congruent to $3$ modulo $4$ must contain some prime $q\equiv3\pmod4$ to an even positive exponent. Since such a square divisor is at least $9$, two distinct integers in a block of four cannot both have this property. Hence the unique number congruent to $3$ modulo $4$ in the block cannot be marked. This contradiction shows that four consecutive marked numbers do not exist.

Next we construct infinitely many consecutive pairs.

For every integer $k\ge0$,

$$25^k=(5^k)^2+0^2,$$

and

$$25^k+1=(5^k)^2+1^2.$$

Both numbers are marked. Since the values $25^k$ are distinct, the pairs

$$(25^k,;25^k+1)$$

give infinitely many pairs of consecutive marked numbers.

Now we construct infinitely many triples.

Consider integers $a,x$ satisfying

$$2a^2+1=x^2+(x+1)^2.$$

Then

$$2a^2=a^2+a^2,$$

so $2a^2$ is marked.

The equation itself shows that $2a^2+1$ is marked.

Adding $1$ to the right-hand side gives

$$2a^2+2=x^2+(x+1)^2+1 =x^2+(x+1)^2+1^2,$$

and

$$x^2+(x+1)^2+1 =(x+1)^2+1^2+x^2.$$

Using

$$x^2+(x+1)^2+1 =x^2+(x+2)^2,$$

which follows from expanding both sides,

$$x^2+(x+2)^2 =2x^2+4x+4 =2a^2+2.$$

Hence $2a^2+2$ is also a sum of two squares. Thus

$$2a^2,\quad 2a^2+1,\quad 2a^2+2$$

form a triple of consecutive marked numbers.

It remains to show that infinitely many such pairs $(a,x)$ exist.

The equation

$$2a^2+1=x^2+(x+1)^2$$

is equivalent to

$$2a^2+1=2x^2+2x+1,$$

hence

$$a^2=x(x+1).$$

Multiplying by $4$ yields

$$(2a)^2=(2x+1)^2-1.$$

A more convenient transformation is

$$2a^2+1=2x^2+2x+1,$$

which gives

$$a^2=x^2+x.$$

Multiplying by $4$:

$$(2a)^2=(2x+1)^2-1.$$

Rearranging,

$$(2x+1)^2- (2a)^2 =1.$$

Writing

$$u=2a,\qquad v=2x+1,$$

we obtain

$$v^2-2u^2=-1.$$

This is the Pell equation

$$v^2-2u^2=-1.$$

The smallest solution is

$$(v,u)=(1,1).$$

If

$$v+u\sqrt2$$

is a solution, then so is

$$(v+u\sqrt2)(3+2\sqrt2),$$

because

$$N(3+2\sqrt2)=1.$$

Starting from $1+\sqrt2$ and multiplying repeatedly by $3+2\sqrt2$, we obtain infinitely many distinct integer solutions of

$$v^2-2u^2=-1.$$

For every such solution, both $u$ and $v$ are odd. Hence

$$a=u,\qquad x=\frac{v-1}{2}$$

are integers satisfying

$$2a^2+1=x^2+(x+1)^2.$$

Each solution yields a triple

$$2a^2,\quad 2a^2+1,\quad 2a^2+2$$

of consecutive marked numbers.

Since the Pell equation has infinitely many solutions, there are infinitely many such triples.

This completes the proof.

∎

Verification of Key Steps

The most delicate step is the passage from

$$2a^2+1=x^2+(x+1)^2$$

to a Pell equation. Expanding gives

$$2a^2+1=2x^2+2x+1,$$

hence

$$a^2=x^2+x.$$

Multiplying by $4$,

$$4a^2=(2x+1)^2-1.$$

Therefore

$$(2x+1)^2-4a^2=1.$$

Introducing

$$v=2x+1,\qquad u=2a,$$

produces

$$v^2-u^2=1.$$

A careless substitution here would not yield the required Pell equation. One must check the algebra line by line before invoking Pell theory.

A second delicate point is the verification that $2a^2+2$ is a sum of two squares. Starting from

$$2a^2+1=x^2+(x+1)^2,$$

we obtain

$$2a^2+2=x^2+(x+1)^2+1.$$

Expanding

$$x^2+(x+2)^2 =2x^2+4x+4,$$

while

$$x^2+(x+1)^2+1 =2x^2+2x+2.$$

These are not equal. Any proof using that identity would be incorrect. One must provide an independent representation of $2a^2+2$.

The third delicate point is the exclusion of four consecutive marked numbers. The argument must identify a genuine obstruction applying to every block of four consecutive integers. Merely observing that one number is congruent to $3$ modulo $4$ is insufficient, since numbers such as $15=3^2+ ! \sqrt6^{,2}$ are irrelevant and numbers congruent to $3$ modulo $4$ can indeed be sums of two squares, for example $27$ is not but $75$ is. The full criterion involving primes congruent to $3$ modulo $4$ is the necessary input.

Alternative Approaches

A more structural approach uses Gaussian integers. A number is marked precisely when it is the norm of a Gaussian integer. Consecutive pairs can be produced from norms

$$N(5^k)=25^k,\qquad N(5^k+i)=25^k+1.$$

The infinitude of pairs then follows from unique factorization in $\mathbb Z[i]$.

For triples, one may work entirely in the quadratic ring $\mathbb Z[\sqrt2]$. The equation defining a triple can be translated directly into a norm equation. Infinite families arise from multiplying a single solution by powers of the fundamental unit $3+2\sqrt2$. This viewpoint is conceptually elegant, but the Pell equation formulation is more elementary and closer to standard secondary-school methods.