Prove that there do not exist positive integers $x$ and $y$ with $x^2 - y^2 = n$

I'm working on a homework problem that is as follows:

Suppose that $n$ is a positive even integer with $n/2$ odd. Prove that there do not exist positive integers $x$ and $y$ with $x^2 - y^2 = n$.

It looked like a good candidate for proof by contradiction. So I know that I still assume the argument "$n$ is a positive even integer with $n/2$ odd" but will try to show that there exists positive integers $x$ and $y$ with $x^2 - y^2 = n$, and if this reaches a contradiction then I have proven the original conjecture.

So I started with the $n/2$ is odd and rewrote it as $n/2 = 2k+1$, for some $k$ in the integers.

Then I knew that $n = 4k+2$, and then tried so equate that with $x^2 - y^2 = 4k+2$.

EDIT: I then recognized that $x^2 - y^2$ is equivalent to $(x + y)(x - y)$ but that doesn't seem to be very helpful, because if you divide one or the other out you get a term on the RHS in terms of k and x and y.

I'm going to keep playing with it but I don't really have any good strategies going forward. Any help is appreciated!

• $x^2-y^2=(x-y)(x+y)$ Commented Jul 29, 2012 at 21:49
• $(x-y)(x+y)$ - both even or both odd. Commented Jul 29, 2012 at 21:51
• Also, $x^2$ is even if and only if $x$ is even, same for $y.$ Oh: the first thing is that your $n$ is not divisible by 4. Commented Jul 29, 2012 at 21:51
• Dear Augustus, If you want to argue by contradiction, you do not "try to show that there exists positive integers $x$ and $y$ with ...", but rather you assume that such $x$ and $y$ exist. Regards, Commented Jul 30, 2012 at 3:34
• My bad Matt E. slip of the tongue. Thanks greatly for the correction Commented Jul 30, 2012 at 4:07

A more or less mechanical approach is to work modulo $4$. Note that for any integer $k$, $k^2\equiv 0 \pmod{4}$ or $k^2\equiv 1\pmod{4}$.

So, modulo $4$, $x^2-y^2$ can only take on the values $0$, $1$, and $-1$.

More basic, and more useful, is to suppose that $x^2-y^2=n$. Then $(x-y)(x+y)=n$. Note that for any integers $x$ and $y$, the numbers $x-y$ and $x+y$ are both even or both odd. (If we want a proof, their difference $2y$ is even.)

In neither case is $(x-y)(x+y)$ twice an odd integer. You started along these lines. Note that you were one step from the end.

Remark: The reason the second idea is more useful is that when it comes to solving $x^2-y^2=n$, we express $n$ as a product $st$ of integers of the same parity, and solve the system $x-y=s$, $x+y=t$. The solution is $x=\frac{s+t}{2}$, $y=\frac{s-t}{2}$. If $n$ is twice an odd integer, then this process breaks down, because one of $s$ and $t$ will be odd and the other even, so we do not get integers $x$ and $y$.

• I like this a lot. +1 Commented Jul 29, 2012 at 21:54
• I don't understand the congruence that you have written for the first part before the line break. How is it that you arrive at 4 divides $k^2$ or 4 divides $k^2 - 1$? Commented Jul 29, 2012 at 22:06
• @Augustus: You might just calculate it - if you have integers of the form $4k, 4k+1, 4k+2, 4k+3$ and square them, they'll fall into the two residue classes $0\pmod 4$ or $1 \pmod 4$. Alternately, if you're familiar with quadratic residues, then you could use that approach. Commented Jul 29, 2012 at 22:11
• If $k$ is even, say $k=2q$, then $k^2=4q^2$, so $4$ divides $k^2$. If $k$ is even, say $k=2q+1$. then $k^2=(2q+1)^2=4q^2+4q+1=4(q^2+q)+1$, which is $1$ more than a multiple of $4$. Actually, $q^2+q$ is even, so indeed $k^2$ is $1$ more than a multiple of $8$, an often useful fact. Commented Jul 29, 2012 at 22:11
• Okay thanks alot! Commented Jul 29, 2012 at 22:14

HINT

1. $x^2 - y^2 = (x-y)(x+y)$
2. If $x-y$ is even, then so is $x+y$

For every integer $x$, $x^2=0$ or $1\pmod{4}$. Hence, for every integers $x$ and $y$, $x^2-y^2=1$ or $0$ or $-1\pmod{4}$. On the other hand, if $n=2(2k+1)$ for some integer $k$, $n=2\pmod{4}$. Hence, $x^2-y^2=n\pmod{4}$ with $n$ twice an odd integer is impossible.

You look at $x^2-y^2=(x+y)(x-y)$, and this factoring can be used to complete the proof.

Since $n$ is even, at least one of $(x+y),(x-y)$ must be even, but then since $n/2$ is odd, the other must be odd. That would mean $(x+y)+(x-y)=2x$ is also odd, which contradicts the existence of integer solutions.

• Added as a generic version of my specific answer when $n=2002$ Commented Mar 21, 2017 at 18:39

$$\rm\begin{eqnarray}{\bf Hint\!\!:}\rm\ \ if\ prime\,\ p\:|\:a\!-\!b\,\ then\,\ p\:|\:ab\:&\Rightarrow&\:\rm p^2\:|\:ab,\ \,by\ \ a\equiv b\!\!\!\pmod{\!p} \\ \rm Therefore\ we\ deduce\ that\,\ 2\:|\:x^2\!-\!y^2&\Rightarrow&\:\rm\ \ 4\:|\:x^2\!-\!y^2\ \ for\ \ p=2,\,\ a,b = x\pm y\end{eqnarray}$$

If $x^2-y^2= N$ and $N/2$ is odd this diophantine equation has no solutions. In fact you can rewrite this equation: $(x-y)(x+y)=N$, but $N$ is even and it is divisibile for $2$ then only one factor is even. So solving this equation with this formula: $x=(p+q)/2$ and $y=(p-q)/2$, where $pq=N$ you obtain two rational solutions.

Since for any $$a^2-b^2=(a+b)(a-b)=d_1 \cdot d_2=N$$ We have \begin{align} \begin{cases} d_1&=a+b \\ d_2&=a-b \end{cases} \ \ \ \implies \ \ \ \begin{cases} a&=\frac{d_1+d_2}{2}\\ b&=\frac{d_1-d_2}{2} \end{cases} \end{align} \ \ \implies \text{the identity}

$$\left(\frac{d_1+d_2}{2}\right)^2-\left(\frac{d_1-d_2}{2}\right)^2=d_1\cdot d_2$$

Meaning that $N$ needs to meet the requirement that it can be factored into two divisors of the same parity. This can be done for any odd number, even prime, as $d_1=\text{prime}$ and $d_2=1$. But not necessarily every even. If the power of 2 in the prime factorization of N is greater than 1, then you have enough 2's to distribute to both divisors, $d_1$ and $d_2$. But if the power of 2 in the prime factorization of N is equal to 1 (as it would be if $\frac{n}{2}$ is odd), then that 2 will have to go in one of the divisors leaving the other odd, resulting in an odd sum or difference, resulting in a non-integer.

Your equation is $$x^2-y^2=n\textrm{, }n>0.\tag 1$$ I will show that

THEOREM 1.

1) The number of solutions of (1) for any positive integer $$n$$ is $$r(n)=\sum_{d|n}\textrm{abs}\left((-1)^d+(-1)^{n/d}\right).\tag 2$$

2) If $$n=2P$$, $$(2,P)=1$$, then (1) is imposible and the oposite.

PROOF.

1) For this assume that $$r(n)$$ is the number of representations of any positive integer $$n$$ in the form (1), with $$x,y\in\textbf{Z}$$. We can write $$x^2-y^2=(x-y)(x+y)$$ and setting $$A=x-y$$, $$B=x+y$$, we have such representations iff $$x=\frac{A+B}{2}$$ and $$y=\frac{A-B}{2}$$ i.e that is iff $$AB=n$$ and $$A,B$$ both even or both odd. Hence we can write that, for any positive integer $$n\neq 0$$, the number of solutions of (2) is $$r(n)=2\sum_{ \begin{array}{cc} 1\leq A,B\leq n\\ AB=n\\ \frac{A+B}{2}=\textrm{integer}\\ \frac{A-B}{2}=\textrm{integer} \end{array} }1=2\sum_{k|n}\left|\frac{(-1)^k+(-1)^{n/k}}{2}\right|.$$ Hence finaly $$r(n)=\sum_{d|n}\textrm{abs}\left((-1)^d+(-1)^{n/d}\right).$$ 2) Moreover about the second state of the theorem we have: When $$n$$ is even with the prime decomposition $$n=2p_1^{a_1}p_2^{a_2}\ldots p_s^{a_s}$$, $$p_1, $$p_i=$$primes>2, $$i=1,2,\ldots,s$$, then in each $$d|n$$, we have $$d=$$even and $$n/d=$$odd or $$d=$$odd and $$n/d=$$even. Hence all $$\textrm{abs}\left((-1)^d+(-1)^{n/d}\right)=0$$ and $$r(n)=0$$. QED