Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
I was close to Cofopuff's solution but was stuck in the combinations...... – Swapnanil Saha Aug 9 '12 at 13:53
up vote 6 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|cite|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


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.