As the title reads. Given an integer $m\ge1$, how to calculate the number of integer $n$'s ($1\le n\le 2m$) such that $4m^2-n^2$ is a perfect square? Thank you~

Update: Further, how many pairs $(n,z)$ satisfy $4m^2-n^2=3z^2$ ?

  • 1
    $\begingroup$ You want to solve $n^2 + z^2 = (2m)^2$ in $\mathbb{Z}.$ Do you know how to generate pythagorean triples? $\endgroup$ – jspecter Oct 17 '11 at 14:05
  • $\begingroup$ Ah, $(a^2-b^2)^2+(2ab)^2=(a^2+b^2)^2$. So I have to find all $(a,b)$'s such that $a^2+b^2=2m$. $\endgroup$ – ziyuang Oct 17 '11 at 14:15
  • $\begingroup$ A non-pythagorean question is added. $\endgroup$ – ziyuang Oct 17 '11 at 14:53
  • $\begingroup$ @ziyuang: The Pythagorean triples are not quite given by the formula you quoted. With some restrictions you get the primitive triples. There is a formula that for any $w$ gives the number of integer solutions of $x^2+y^2=w$. It involves factoring $w$, what mostly matters is the primes of the form $4k+1$ in the factorization of $w$. $\endgroup$ – André Nicolas Oct 17 '11 at 15:20

There is a large literature on the number of representations of $k$ as a sum of two squares. The formulas are simplest if we count the ordered pairs $(x,y)$ of integers, which need not be $\ge 0$, such that $x^2+y^2=k$. The number of such representations is usually denoted in the literature by $r_2(k)$, or more simply $r(n)$. But there are also related expressions that count the number of unordered pairs of non-negative integers $x$, $y$ such that $x^2+y^2=k$. Your question asks about unordered pairs of non-negative integers, in the case $k=4m^2$.

Most books on elementary number theory have some discussion of the number of representations as a sum of two squares. There is also quite a bit of online information. One might begin by looking at Wolfram MathWorld.

The standard general formula can be easily specialized to the case $k=4m^2$. Let $$m=C p_1^{a_1}p_2^{a_2} \cdots p_s^{a_s},$$ where the $p_i$ are distinct primes of the form $4u+1$, and $C$ is not divisible by any prime of the form $4u+1$. Then the number of unordered pairs $x$, $y$ of non-negative integers such that $x^2+y^2=4m^2$ is equal to $$\frac{(2p_1+1)(2p_2+1)\cdots (2p_s+1)+1}{2}.$$

For extremely large $m$, the above formula, though explicit, may not be very helpful, because of the computational cost of factoring.

| cite | improve this answer | |
  • $\begingroup$ Thank you, @André Nicolas, it's a nice answer and reference. Is there literature on decomposing an integer into a perfect square and a prime multiple of another perfect square (Just as the second part of the question)? $\endgroup$ – ziyuang Oct 18 '11 at 15:01
  • 1
    $\begingroup$ Yes, lots of literature. Some primes give more trouble than others, $p=3$ is particularly easy. The primes of the form $4u+1$ that we used in the two squares problem are, roughly speaking, replaced by primes of the form $6k+1$. What we are really doing is factoring $m^2$ (yes) as $(x-\sqrt{-3}y)(x+\sqrt{-3}y)$, instead of factoring $4m^2$ over the Gaussian integers. Thought of writing out an answer, the $3$ case is well-known, must be in lots of places on the Web. But it is also in books, when I get to the library (not real soon) I may be able to give a reference. $\endgroup$ – André Nicolas Oct 18 '11 at 15:29

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.