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.

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

 
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.