1
$\begingroup$

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$ ?

  • 0
    @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$.2011-10-17

1 Answers 1

3

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.

  • 1
    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.2011-10-18