# How many values of $x\in\mathbb Z^+,x<99$ are there such that $m,n\in\mathbb Z$ and $m^2-n^2=x$ is possible?

How many values of $$x\in\mathbb Z^+,x<99$$ are there such that $$m,n\in\mathbb Z$$ and $$m^2-n^2=x$$ is possible?

So what I'm trying to find here is the number of integers between $$1$$ and $$98$$ inclusive such that that integer can be expressed as the difference of two squares. I know that all odd numbers can be expressed as the difference between to consecutive squares, so the answer is at least $$98/2=49$$, but I don't really see a way to continue from here. Maybe I can utilize Pythagorean Theorem somehow? Thanks for the help. Also I'm not too sure which topic this question falls under so if someone could edit the tags that would be great.

• $m^2-n^2=(m-n)(m+n)$ – player3236 Sep 14 '20 at 16:48
• @player3236 Yes I have noticed that but I'm not sure how I can utilize this information to solve the problem. – Aiden Chow Sep 14 '20 at 16:49
• Just take the differences of squares of moderate size. So $3=2^2-1^2$ is possible, etc. You can use $x=(m+n)(m-n)$ to derive a contradiction for certain $x$, like $x=2$. – Dietrich Burde Sep 14 '20 at 16:50
• @DietrichBurde I'm still not seeing it. How do I know which values of $x$ to test, and how exactly do you get a contradiction from $(m+n)(m-n)$ for certain values of $x$? – Aiden Chow Sep 14 '20 at 16:53
• Indeed these are the only ones. – player3236 Sep 14 '20 at 17:00

There are two ways to generate an even number as the difference of two squares: $$m,n$$ are either both even or both odd. If $$m=2k$$ and $$n=2l$$, then $$m^2-n^2=4(k^2-l^2)$$. This immediately tells us that all numbers $$4x$$, $$x$$ odd, are possible.

If $$m=2k+1$$ and $$n=2l+1$$: $$m^2-n^2=4(k^2-l^2+k-l)=4(k-l)(k+l+1)$$ and every even number $$2x$$ may be written in the form $$(k-l)(k+l+1)$$ by setting $$k=x$$ and $$l=x-1$$. So all numbers $$4x$$, $$x$$ even, are possible.

In conclusion, the numbers that are the difference of two squares are odd numbers and multiples of $$4$$. There are $$49+\lfloor98/4\rfloor=49+24=73$$ such numbers in the given range.

I'll supplement the other proof by showing also that numbers that are even but not divisible by $$4$$ cannot be expressed as a difference of squares of integers.

Suppose $$x = m^2-n^2 = (m-n)(m+n)$$.

Let $$p,q\in\mathbb Z$$ such that $$x = pq$$.

By letting $$p = m-n$$, $$q=m+n$$, we can express $$x$$ as a difference of squares.

However this requires $$p+q = 2m, q-p = 2n$$ to both be even.

This is acheived only if both $$p,q$$ are even or odd.

If both $$p,q$$ are even, $$x$$ is divisible by $$4$$.

If both $$p,q$$ are odd, $$x$$ is also odd.

If $$x$$ is even but not divisible by $$4$$, it must be a product of an odd number and an even number.

Then $$p+q$$ and $$q-p$$ must be odd, which does not fulfil our requirement.

This method is also constructive: any factorization of $$x$$ gives a solution to the difference of squares.

watch this!

If $$x=2h+1$$ is odd then $$x = 1*(2h+1)= ([h+1]-h)([h+1]+h) =(h+1)^2 - h^2$$ so every odd number is difference of square.

If we want to be a bit more creative if $$x = j*k$$ an odd composite then $$j=\frac {j+k}2 + {j-k}2$$ and $$k = \frac {j+k}2-\frac {j-k}2$$ so $$x = (m+n)(m-n) = m^2 - n^2$$ if $$m=\frac {j+k}2$$ (which is an integer as both $$j,k$$ are odd) and $$n = \frac {j-k}2$$ (ditot).

So every odd number will work.

If $$x = 2w$$ and $$w$$ is odd, then if $$x = m^2 -n^2 = (m-n)(m+n)$$ then one of $$m+n$$ or $$n-m$$ is even and the other is not. $$m+n = (m-n) + 2n$$ so if $$m-n$$ is even or odd then so is $$m+n =(m-n)+2n$$. so that is impossible.

So every number that is even but not divisible by $$4$$ will not work.

Induction time!

Now if $$w= m^2- n^2$$ is possible, and $$x= 4w$$ then $$4x = (2m)^2 - (2n)^2$$ is will work.

And note if $$w = m^2 - n^2= (m-n)(m+n)$$ then $$8w = 2*4(m-n)(m+n)=(2m-2n)(4m+4m) = [(3m+n)-(m+3n)][(3m+n) + (m+3n)] = (3m+n)^2 - (m+3n)^2$$ will work.

So by induction, if $$w=m^2 - n^2$$ will work then $$2^kw$$ will work if $$k$$ is even, or if $$k$$ is a multiple of $$3$$ or $$k$$ is a sum of an even number and a multiple of $$3$$. But that can be any positive integer greater than $$1$$.

And as $$h$$ odd will work, and $$2h; h$$ odd will not, then $$2^kh=4(2^{k-1} h); h$$ odd$$; k\ge 2$$ will work.

=====

So the numbers that can be so written are:

Every odd number, every multiple of $$4$$, but no number that is even but not divisible by $$4$$.

Using Eudlid's formula $$\quad A=m^2-k^2,\quad B=2mk,\quad C=m^2+k^2\quad$$ or any other, we know that the value of $$A$$ can be any odd number except $$1$$, i.e. $$A\ge3$$. This means that, under $$99$$, there are $$98/2-1=48$$ odd values of $$A$$.

It also happens that, with this formula ––the only one that uses $$m^2-k^2$$–– $$A$$ can be any multiple of $$4$$ greater than $$4$$ such as $$f(3,1)=(8,6,10)\quad f(4,2)=(12,16,20)\quad f(5,3)=(16,30,34)\quad...\quad f(10,2)=(96,40,104)$$

Note $$\quad f(2,0)=(4,0,4)\qquad$$ but this is a trivial triple so most people do not treat it as valid.

This means that there are $$96/4-1=24-1=23$$ even values of $$A$$ that can be generated by $$m^2-k^2$$ for $$A<99$$. The total is $$48+23=71$$.