7
$\begingroup$

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!

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

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

$\endgroup$
  • $\begingroup$ I like this a lot. +1 $\endgroup$ – davidlowryduda Jul 29 '12 at 21:54
  • $\begingroup$ 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$? $\endgroup$ – Arthur Collé Jul 29 '12 at 22:06
  • $\begingroup$ @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. $\endgroup$ – davidlowryduda Jul 29 '12 at 22:11
  • $\begingroup$ 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. $\endgroup$ – André Nicolas Jul 29 '12 at 22:11
  • $\begingroup$ Okay thanks alot! $\endgroup$ – Arthur Collé Jul 29 '12 at 22:14
7
$\begingroup$

HINT

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

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Added as a generic version of my specific answer when $n=2002$ $\endgroup$ – Joffan Mar 21 '17 at 18:39
1
$\begingroup$

$\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}$

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

1 4 9 16 25

3 5 7 9

the difference of every square is an odd number. If N is even, then for it to be the difference of two squares it must be the sum of an even number of consecutive odd numbers.

3+5=8,,,,,,, 5+7=12 ,,,,,,,, 7+9=16

3+5+7+9=24 ,,,,,,,, 5+7+9+11=32 ,,,,,,,, 7+9+11+13=40

The sequence of the sums of these can be written as 4n+4 and 8n+16 respectively which we can then write as 4(n+1) and 4(2n+4) respectively. The sequence of the sums of any even amount of consecutive odd numbers can be written as 4(kn+k^2) with k being half the amount of consecutive odd numbers. So,

4(kn+k^2)=N

If N is even and when divided by 2 gives an odd number, it is not divisble by 4, so either k or n will not be integers, so N cannot be written as the sum of an even number of consecutive odd numbers.

Therefore,

any even number not divisble by 4 cannot be written as the difference of two squares.

$\endgroup$
  • $\begingroup$ Hi Leosha you should use LaTeX in your answers in this site as it is easier to read. $\endgroup$ – i9Fn Mar 19 '17 at 10:44
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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_2<\ldots<p_s$, $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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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