Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
2  
$x^2-y^2=(x-y)(x+y)$ –  Chris Eagle Jul 29 '12 at 21:49
3  
$(x-y)(x+y)$ - both even or both odd. –  Old John Jul 29 '12 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. –  Will Jagy Jul 29 '12 at 21:51
1  
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, –  Matt E Jul 30 '12 at 3:34
    
My bad Matt E. slip of the tongue. Thanks greatly for the correction –  Arthur Collé Jul 30 '12 at 4:07

5 Answers 5

up vote 15 down vote accepted

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

share|improve this answer
    
I like this a lot. +1 –  mixedmath Jul 29 '12 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$? –  Arthur Collé Jul 29 '12 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. –  mixedmath Jul 29 '12 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. –  André Nicolas Jul 29 '12 at 22:11
    
Okay thanks alot! –  Arthur Collé Jul 29 '12 at 22:14

HINT

  1. $x^2 - y^2 = (x-y)(x+y)$
  2. If $x-y$ is even, then so is $x+y$
share|improve this answer

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.

share|improve this answer

$\rm\begin{eqnarray}{\bf Hint}\,\ \ \ If\ prime\,\ p\:|\:a\!-\!b\,\ then\,\ p\:|\:ab\:&\Rightarrow&\:\rm p^2\:|\:ab \\ \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}$

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.