Exercise 1.3.35* ($n = x^2 - y^2$)

Proof. Let $n$ be a non negative integer.

(if we accept $n<0$, then some other numbers as $-1,-4,\dots$ have also a unique representation.)

(a)

Existence. Assume that $n=x^2-y^2$ for some non negative integers $x,y$. For every integer $x$, $x^2\equiv 0,1(\mathit{mod}4)$, so $-y^2\equiv 0,3(\mathit{mod}4)$, and $x^2-y^2\equiv 0,1,3(\mathit{mod}4)$. Thus $n$ is not of the form $4k+2$. In other words, $n$ is odd or is a multiple of $4$.

Conversely assume that $n$ is odd or is a multiple of $4$.

• If $n$ is odd, then

  $$\begin{array}{llll}\hfill n& ={\left(\frac{n+1}{2}\right)}^2-{\left(\frac{n-1}{2}\right)}^2& \hfill & \\ \hfill & & \hfill \end{array}$$

  so that $n=x^2-y^2$, where $x=\frac{n+1}{2}$ and $y=\frac{n-1}{2}$ are non negative integers.

• If $4n$ is a multiple of $4$, then

  $$\begin{array}{llll}\hfill n& ={\left(\frac{n}{4}+1\right)}^2-{\left(\frac{n}{4}-1\right)}^2& \hfill & \\ \hfill & ={\left|\frac{n}{4}+1\right|}^2-{\left|\frac{n}{4}-1\right|}^2& \hfill & \end{array}$$

  so that $n=x^2-y^2$, where $x=\left|\frac{n}{4}+1\right|$ and $y=\left|\frac{n}{4}-1\right|$ are non negative integers.

(b)

Unicity. Assume that $n=1,4,$ an odd prime, or four times a prime. We know from part (a) that $n=x^2-y^2$ for some non negative integers $x,y$. We will show that this representation is unique.

• If $n=1$, then

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

  Since $x^2=y^2+1>y^2$, and $x\ge 0,y\ge 0$, we obtain $x>y$, thus $0<x-y\le x+y$. Therefore $x-y=1$ and $x+y=1$. This gives $x=[(x+y)+(x-y)]∕2=1,y=([(x+y)-(x-y)]∕2$, so that the decomposition is unique.

• If $n=4$, then

  $$4=x^2-y^2=(x-y)(x+y).$$

  As previously, $0<x-y\le x+y$, so $x-y=1,x+y=4$, or $x-y=2,x+y=2$. in the first case, $x=5∕2$ is not an integer, thus $x=2,y=0$: the decomposition is unique.

• If $n=p$ is an odd prime,

  $$p=x^2-y^2=(x-y)(x+y),$$

  where $0<x-y\le x+y$. Since $p$ is prime, $x-y=1,x+y=p$, thus $x=(p+1)∕2,y=(p-1)∕2$: the decomposition is unique.

• If $n=8$ ( $n=4\times 2$, where $2$ is prime), then

  $$8=x^2-y^2=(x-y)(x+y),$$

  where $0<x-y\le x+y$. The divisors of $8$ are $1,2,4,8$, and $x-y,x+y$ are of same parity, thus $x-y=2,x+y=4$, so $x=3,y=1$: the decomposition is unique.

• If $n=4p$, where $p$ is an odd prime, then

  $$4p=x^2-y^2=(x-y)(x+y),$$

  where $0<x-y\le x+y$, and $x-y,x+y$ are of same parity. The divisors of $4p$ are $1,2,4,p,2p,4p$. Therefore, $x,y$ satisfy $x-y=2,x+y=2p$: the decomposition is unique.

Conversely, assume that $n$ is odd or is a multiple of $4$, but $n\ne 1$, $n\ne 4$, and $n$ is not an odd prime, and is not four times a prime. We want to prove that $n$ has at least two distinct decompositions of the form $n=x^2-y^2$.

Note $0=1^2-1^2=2^2-2^2$ has two decompositions. We suppose now $n>0$.

Examine first the case where $n$ is odd. Since $n\ne 0,n\ne 1$, and $n$ is not a prime, $n$ is of the form

$$n=\mathit{pq},$$

where $p$ is an odd prime, and $q>1$ is odd. Then the equalities

$$n={\left(\frac{n+1}{2}\right)}^2-{\left(\frac{n-1}{2}\right)}^2,n={\left(\frac{p+q}{2}\right)}^2-{\left(\frac{p-q}{2}\right)}^2$$

give two distinct decompositions of $n$: if $\left(\frac{n+1}{2},\frac{n-1}{2}\right)=\left(\frac{p+q}{2},\frac{p-q}{2}\right)$, then $n=p,q=1$, and $n$ is a prime: this is a contradiction.

Examine now the case where $n=4k$ is a multiple of $4$, where $k>0$. By hypothesis, $k\ne 1$, and $k$ is not a prime, thus $k$ is composite, so $k=\mathit{uv},v\ge u>1$. Then

$$n=4\mathit{uv}={(\mathit{uv}+1)}^2-{(\mathit{uv}-1)}^2,n=4\mathit{uv}={(v+u)}^2-{(v-u)}^2$$

give two distinct decompositions of $n$: if $(\mathit{uv}+1,\mathit{uv}-1)=(v+u,v-u)$, then $\mathit{uv}=v,u=1$, so $u=v=1$: this is a contradiction.

To conclude: If $n\ge 0$ is an integer,

There is no representation of $n$ of the form $n=x^2-y^2$ if $n$ is even but is not a multiple of $4$.

There is exactly one representation if and only if $n=1,4,$ an odd prime, or four times a prime.

There are several distinct representations if $n$ is odd or is a multiple of $4$, but $n\ne 1$, $n\ne 4$, and $n$ is not an odd prime, and is not four times a prime. □