2
$\begingroup$

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.

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

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.

$\endgroup$
  • $\begingroup$ I don't think I fully understand your counting..." For the odds, count $1$, plus ... plus all primes $≤24$. There are $10$ such primes." $\endgroup$ – Quixotic Aug 10 '11 at 9:48
  • $\begingroup$ That's because I can't count. There are $9$ primes less than $25$. Thanks! $\endgroup$ – André Nicolas Aug 10 '11 at 11:42
  • $\begingroup$ Andre,take a look at this $\endgroup$ – Quixotic Jan 10 '12 at 17:26
  • 1
    $\begingroup$ @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. $\endgroup$ – André Nicolas Jan 10 '12 at 17:38
  • $\begingroup$ Yes, when I find this (the url one) problem I thought about this one (related) hence thought of posting it here :-) $\endgroup$ – Quixotic Jan 10 '12 at 21:11
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

I came across a question in a Singapore Math Olympiad Grade 8 paper which asked " How many 2-digit positive integers can be expressed as the difference of two perfect square numbers? I am sharing my solution here.

First of all the positive integer, Say N > 9 and N<100

We will approach this problem with assuming the possible count of N when N is an odd number and then when N is an even number.

Lets assume first that N is an odd number so N = 2K+1, where K is any whole number starting from 0.

Now N = 2K+1=(K+1+K)1= {(K+1)+K)}{(K+1)-K}=(K+1)^2-K^2. This means, All N which are odd numbers in the form of 2K+1 can be represented as difference of two perfect squares of K+1 and K. From the range of N, we further get that there are {(99-11)/2+1}= 45 odd numbers which can be represented as difference of perfect squares where largest N is 99 and smallest is 11 and largest K is 49 and smallest K is 5. So if we get odd number N=2K+1, we can quickly find out K+1 and K as K = (N-1)/2.

So we have got 45 two digits odd numbers which can represent the difference of two perfect squares.

Now lets consider N as an even number and lets assume N = a^2-b^2 where a and b are whole numbers.

Now lets assume N = a^2-b^2 = (a+b)*(a-b) where a>b and try to find out what conditions will fullfill this. Now for N to be an even number either both a and b has to be even (Case 1) or both of them have to be odd (Case 2). If one of them is even and one of them is odd then both a+b and a-b will be odd and the product of two odd numbers is an odd number which is not the original assumption since N is an even number.

Case 1: Lets say both a and b are odd, therefore we can say that a+b is even and also a-b is even. Now lets assume a=2p+1 and b=2q+1 where p>q.

Therefore, N= (a+b)(a-b) = (2p+1+2q+1)(2p+1-2q-1)= (2p+2q+2)(2p-2q) =4(p+q+1)(p-q). Therefore we can safely say that N has to be a multiple of 4 when a and b are odd numbers. Also, please note that (p+q+1)(p-q) will always be an even number for all all p's and q's and One of them, either (p+q+1) or (p-q) will be even and the other one odd.

In this scenario if even number N is given, we can quickly divide it by 4 and see if it {(p+q+1)(p-q)} is an even number and then see two factor combinations. If the factors have even and odd combination, then you can find p and q from there and further find a = 2p+1 and b = 2q+1. eg. p=4 and q= 3 which gives a= 9 and b = 7 so N = a^2-b^2 = 4(p+q+1)*(p-q) = 81-49 = 32.Please note that this scenario also happens when both a and b are even in some cases so N is not for unique cases of differences of perfect square.

Case 2: Lets say both a and b are even, therefore we can say that a+b is even and also a-b is even. Now lets assume a=2p and b=2q as they are even numbers where p>q and p can be even or odd.

Therefore, N= (a+b)(a-b) = (2p+2q)(2p-2q)= 4*(p^2-q^2). Therefore we can safely say that N has to be a multiple of 4 when a and b are even numbers also.

Here if we know N, we can divide it by 4 and see if p^2-q^2 is an even or odd number. If its an odd number say O which will happen only when one of them is even and the other one odd, then we can find using p=2K+1 and q = K, where K=(O-1)/2. Then we can find a and b which are 2p and 2q respectively.

However, in this case, we might get p^2-q^2 as an even number E also and in that case p and q needs to be figured out as both will be either odd or both will be even. We can use the factor (p+q)*(p-q) to check what values of p and q satisfy for E and where both p & q are either even or odd.

From these two cases of N being and N number we also derived that only multiples of 4 will satisfy the condition. So the highest two digit multiple is 96 and lowest is 12 so there are {(96-12)/4+1)= 22 cases when N is even.

So over all we have 45 odd and 22 even values of N where N is a two digit positive integer and represents the difference of two perfect squares.


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