2
$\begingroup$

An odd positive integer is the product of $n$ distinct primes. In how many ways can it be represented as the difference of two squares?

My formulation of the question: $$x^2 - y^2 = p_1p_2p_3\cdots p_n$$ $$(x+y)(x-y)= p_1p_2p_3\cdots p_n$$ Find the number of pairs $(x,y)$.

With a few test cases I've realized that if all the primes are distinct, then there are exactly $2^n$ numbers which divide the RHS and hence exactly $2^{n-1}$ such pairs since the two numbers multiply to form the RHS. I've checked it till $n=4$. Also, the number of pairs is always equal to or larger than $1$ since every odd number can be expressed as the difference of two successive squares.

I've realized that the above fact must be proved. Though there may be other methods, I have felt that induction on $n$ is a possible way. Please help. I need an intuitive understanding of the question and help on the inductive proof.

By the way, for reasons I don't understand $x$ is always turning out to be odd and $y$ even. It could have been the inverse. Can you explain this?

$\endgroup$
  • $\begingroup$ It is not always $x$ odd $y$ even. For example $15=4^2-1^2=8^2-7^2$. If the product of the primes is of the form $4k+1$, then it is $x$ odd $y$ even, but if the product of the primes is of the form $4k+3$ then it is $x$ even $y$ odd. $\endgroup$ – André Nicolas Apr 8 '16 at 16:22
  • $\begingroup$ @AndreNicolas Great point. Thanks. $\endgroup$ – TheRandomGuy Apr 8 '16 at 16:29
0
$\begingroup$

So, the way I'd think of it intuitively using the following fact

Given any two odd integers, $a,b$, you can find an $x,y$ such that $a=x+y$ and $b=x-y$. To get these $x,y$ you let $x=\frac{a+b}{2}$ and $y=\frac{a-b}{2}$.

This means that you can just think about how to partition the primes. By partitioning your list of primes into two groups, you have picked a pair $(a,b)$ from which you can use the above to obtain $x$ and $y$.

There is a small caveat here: You need $a\neq b$ for the above fact to work the way you want! However, in this problem, that cannot happen because of the Unique Prime Factorization property. If your list of primes were to have repeats, you would have to be more careful.

So, now the question is how can we partition the primes. There are $2^n$ ways to split $n$ objects into $2$ collections. However, there will be a small number of repeats because the partitions $(\{2,3\},\{5,7\})$ and $(\{5,7\},\{2,3\})$ produce the same pair of numbers $x,y$ just switched. This is the only way repeats can occur, and so dividing by $2$ to account for this gives the answer of $2^{n-1}$

$\endgroup$
  • 1
    $\begingroup$ You find integers $x$ and $y$ iff both $a$ and $b$ are the same parity. $\endgroup$ – TheRandomGuy Apr 8 '16 at 16:06
  • $\begingroup$ @Dhruv Ah good point, i can edit that to account for differing parities though. What do you think now? $\endgroup$ – Stella Biderman Apr 8 '16 at 16:08
  • $\begingroup$ @StellaBiderman The claim in the boxquote is still false. Take, for instance, $a=1, b=4$. $\endgroup$ – Erick Wong Apr 8 '16 at 16:34
  • $\begingroup$ When you are trying to prove it for a universal case then it's different but it's clear that both $a$ and $b$ are odd for the question. And hence we can find $x$ and $y$. $\endgroup$ – TheRandomGuy Apr 8 '16 at 16:50
  • $\begingroup$ @Dhruv Oh, hahaha. True. I'll just note that then. $\endgroup$ – Stella Biderman Apr 8 '16 at 16:59

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.