# 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 + 14 = 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 isn't even very big.

Second HINT:

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

-