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.

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

Please explain your approach.

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.

share|improve this question
    
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
add comment

2 Answers 2

up vote 11 down vote accepted

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.

share|improve this answer
    
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
1  
@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
add comment

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

share|improve this answer
add comment

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.