Saturday, January 30, 2016

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?




Please explain your approach.



ADDED: I can determine whether a number could be represented as difference of two squares,say N=a2b2 ,where a,b,NN,which gives N=(a+b)(ab) hence,(a+b) and (ab) 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.



Answer



The answer depends on whether you count 02 as a perfect square or not. For the analysis below, 02 is a perfect square. And we interpret "number below 100" as meaning positive integer below 100. Also, note that 5=3222=(3)222. 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
x2y2=n,that is, of(xy)(x+y)=n.



We must then have
xy=dx+y=nd

where d is a (positive) divisor of n.



Solving for x and y, we obtain
x=d+nd2andy=d+nd2.



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 dn/d, that is, dn. 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 dn 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 dn/d.
This is the same as the number of ways of expressing n=n/4 as a product of d and n/d, where dn/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 99.
There are 24 odd primes less than 100, for a total of 25.




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



So overall 35 numbers qualify.



Comment: If we don't allow 02 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 p2 now only has one representation, since p202 is not allowed, so it should be counted. Similarly, in the even case, now 4p2 only has one representation.


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection f:AB and I want to get bijection. Can I just resting codomain to f(A)? I know that every function i...