Take the 2-minute tour ×

If a number can be expressed as a product of n unique primes, in how many ways can the number be expressed as a difference of two squares?

share|improve this question
What have you tried? –  Qiaochu Yuan Aug 9 '12 at 13:44
I was close to Cofopuff's solution but was stuck in the combinations...... –  Swapnanil Saha Aug 9 '12 at 13:53

1 Answer 1

up vote 5 down vote accepted

Write $m = p_1 * ... * p_n$ and for now assume each $p_i$ is odd. Then each factorization of $m = a*b$ into a pair of odd numbers $(a,b)$ gives a representation $$m = ab = (\frac{a+b}{2} + \frac{a-b}{2})(\frac{a+b}{2} - \frac{a-b}{2}) = (\frac{a+b}{2})^2 - (\frac{a-b}{2})^2$$ and vice versa. So you need to consider all possible pairs of factors $(a,b)$ (where order doesn't matter). There are $\frac{1}{2}(\binom{n}{0} + \binom{n}{1} + ... + \binom{n}{n}) = 2^{n-1}$ of these.

If one of the $p_i$ is two, then there are no representations: by the unique primes assumptions, $m \equiv 2 \bmod 4$ and all differences of two squares are one of $0,1,3 \bmod 4$.

share|improve this answer
Yes, I was sure 2 cannot be for nonzero solutions. –  Swapnanil Saha Aug 9 '12 at 13:48
@Swapnanil See also the composition law for differences of squares. –  Bill Dubuque Aug 9 '12 at 14:32

Your Answer


