# How many $n$'s can make $4m^2-n^2$ a perfect square? And, triple of a perfect square?

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

-
You want to solve $n^2 + z^2 = (2m)^2$ in $\mathbb{Z}.$ Do you know how to generate pythagorean triples? – jspecter Oct 17 '11 at 14:05
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$. – ziyuang Oct 17 '11 at 14:15
A non-pythagorean question is added. – ziyuang Oct 17 '11 at 14:53
@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$. – 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$.
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.
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. – André Nicolas Oct 18 '11 at 15:29