# How many numbers below $100$ can be expressed as a difference of two perfect squares in only one way?

How many numbers below $100$ can be expressed as a difference of two perfect squares in only one way?

ADDED: I can determine whether a number could be represented as difference of two squares,say $N = a^2-b^2$ ,where $a,b,N \in \mathbb{N}$,which gives $N = (a+b)(a-b)$ hence,$(a+b)$ and $(a-b)$ must be both odd or both even,observing the prime factorization of $N$ we can determine whether it is possible to represent $N$ in that form or not,but I am not sure if I could use this for this problem.

-
Might be useful... – J. M. Aug 10 '11 at 3:19
You're on the right track. Keep thinking. When would such a representation be unique? – Qiaochu Yuan Aug 10 '11 at 3:21
@J. M.:Thanks,but I think that paper is talking about the number of representation $N$ as the difference of two natural numbers. – Quixotic Aug 10 '11 at 3:24

The answer depends on whether you count $0^2$ as a perfect square or not. For the analysis below, $0^2$ is a perfect square. And we interpret "number below $100$" as meaning positive integer below $100$. Also, note that $5=3^2-2^2=(-3)^2-2^2$. Representations will always be non-unique if we allow sign changes. So we rule out using squares of negative integers.

The easy way to solve this problem is to look at $1$ to $99$, one after the other. For each, check whether it satisfies the condition, and keep a running tally. After a little while, we notice some patterns, and then the work is quick. As a partial compromise, we could look up a general result, and use that. But that is not interesting, so we develop all the theory we need.

Let $n$ be a positive integer. We look for non-negative integer solutions of $$x^2-y^2=n, \qquad\text{that is, of}\qquad (x-y)(x+y)=n.$$

We must then have $$x-y=d\qquad x+y=\frac{n}{d}$$ where $d$ is a (positive) divisor of $n$.

Solving for $x$ and $y$, we obtain $$x=\frac{d+\frac{n}{d}}{2}\qquad\text{and}\qquad y=\frac{-d+\frac{n}{d}}{2}.$$

From the above equations, $x$ and $y$ are integers precisely when $d$ and $n/d$ are both even or both odd. And since $y$ must be non-negative, we need to have $d \le n/d$, that is, $d\le \sqrt{n}$. Any factor $d$ of $n$ satisfying those conditions gives us a solution, and different factors yield different solutions.

Thus the number of ways of expressing $n$ as a difference of $2$ squares is precisely the same as the number of divisors $d$ of $n$ such that $d\le \sqrt{n}$ and $d$ and $n/d$ have the same parity. In particular, if $n$ is divisible by $2$ but not by $4$, there is no representation of $n$.

Look first at the case $n$ odd. There is only one factorization of $n$ of the desired type iff $n$ is an odd prime or $n=1$.

Look next at the case $n$ even.
The number of representations of $n$ is the number of ways of splitting $n$ into two even factors $d$ and $n/d$, with $d \le n/d$. This is the same as the number of ways of expressing $n'=n/4$ as a product of $d'$ and $n'/d'$, where $d' \le n'/d'$.

There is only one such factorization precisely if $n'$ is a prime or $n'=1$.

Now counting is easy, though somewhat tedious. For the odds, count $1$, plus the odd primes $\le 99$. There are $24$ odd primes less than $100$, for a total of $25$.

For the evens, count $1$, plus all primes $\le 24$. There are $9$ such primes, giving a total of $10$ even numbers.

So overall $35$ numbers qualify.

Comment: If we don't allow $0^2$ as a perfect square, some changes need to be made. The most obvious ones are that $1$ and $4$ should not be counted. But the situation is more complicated than that. For the odd case, if $p$ is a prime, then $p^2$ now only has one representation, since $p^2-0^2$ is not allowed, so it should be counted. Similarly, in the even case, now $4p^2$ only has one representation.

-
I don't think I fully understand your counting..." For the odds, count $1$, plus ... plus all primes $≤24$. There are $10$ such primes." – Quixotic Aug 10 '11 at 9:48
That's because I can't count. There are $9$ primes less than $25$. Thanks! – André Nicolas Aug 10 '11 at 11:42
Andre,take a look at this – Quixotic Jan 10 '12 at 17:26
@MaX: Thanks. "How many numbers below $n$ can be expressed" is easy to get at without tedious counting, it is just everybody except numbers $\equiv \pmod{4}$. The uniqueness requirement in your question makes it unfortunately necessary to count the primes $<n$. This can be hard to do by hand even when $n$ is only moderately large. – André Nicolas Jan 10 '12 at 17:38
Yes, when I find this (the url one) problem I thought about this one (related) hence thought of posting it here :-) – Quixotic Jan 10 '12 at 21:11

HINT:

The differences between perfect squares conform to a strict pattern.

$1^2 = 1$
$2^2 = 1^2 + 3$
$3^2 = 2^2 + 5 = 1^2 + 8$
$4^2 = 3^2 + 7 = 2^2 + 12 = 1^2 + 15$
$5^2 = 4^2 + 9 = 3^2 + 16 = 2^2 + 21 = 1^2 + 24$

One could write a program to test the answers if you wanted, as above a certain number $m$ (I'll let you find out what that is - though it isn't so bad) the possible differences of it's square with other squares are simply too big. It's okay, too, since this number is not very big.

Second HINT:

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

-

Any number that can be written as the product of two even or two odd integers can be written as the difference of two squared integers. This includes all odd integers, N, because they can be written as 1 x N = N.

Numbers that cannot be written as the difference of two squared integers are all numbers that can be written as 2 x (any product of odd primes). Because they cannot be written as the product of two even or two odd integers.

For uniqueness, only odd numbers which can be written as the product of two odd numbers in only one way, can be written uniquely as the difference of two squared integers. That leaves only odd prime numbers, which can be written as 1 x P.

The only even numbers that can be written uniquely as the difference of two squared integers have the form 4P, because 2 x 2P is the only way of writing the even number as the product of two even numbers.

Proof: Given any number T = a x b, where a and b are either both even or both odd and a < b. [a=b, would require that zero be considered a squared integer]

Define integers N and M as: N = (a+b)/2 and M = N-a = b-N. [Note a + b = 2N]

Then N^2 - M^2 = 1/4(a+b)^2 - (N-a) x (b-N) = a x b = T

If a and b are odd, then the answer is unique only if a or b is the number 1 and the other is a prime number. Because if a=p and b=p’ for example. Then T = a x b = 1x pp’ = p x p’. This would give two different representations: N = (1+ pp’)/2 and N’ = (p +p’)/2.

For even numbers a = 2 and b = 2P, N and M are unique as N = (2+2P)/2 = P+1 and M = N-2 = 2P - N = P-1

So for number less than 100:

Even numbers that are 4 times each odd prime less than 25 = 8 even numbers.

Odd numbers : 1x (all odd primes less than 100) = 24

Total = 8 even + 24 odd = 32 numbers less than 100 that can be represented uniquely as the difference of two squared integers.

If we allowed 0^2 as a perfect square as was suggested by others, corresponding to a=b so T=a^2, then every number, T, that is a perfect square,must be considered, because if T= a^2, then a^2 - 0^2 = T. None of these would be unique however.

If T is odd, then, besides T=a x a, we also have T = 1 x a^2, giving N=(1+a^2)/2, and M=N-1=a^2 - N’ = (a^2-1)/2 . None of these cases affect the count of odd numbers above because these cases weren't counted.

If T is even, T=a^2 where a =2c is even. Then T can be written in multiple ways making the rendition not unique: T = 4 c^2 = 2c x 2c = 2 x 2C^2 So N = a or N =(2+2c^2)/2. This does not affect the count of even numbers above since these cases weren't counted.

-

0^2 is a perfect square : Total valid cases - 35
0^2 is a not perfect square : Total valid cases - 38

A computer generated output is available at www.careerbless.com/aptitude/qa/numbers.php.

-