# Number of integer solutions of $2n^2=a^2+b^2$

For a given integer $n$, how many positive integer $(a,b)$ pairs exist which satisfy $2n^2=a^2+b^2$?

In particular, I'm looking for all $n$s where there are exactly 105 solutions. (One solution is $(n,n)$, and there are $2\cdot 52$ other solutions: $(a,b)$ and $(b,a)$ are two different solutions if $a\ne b$.)

I'm sure that there are theorems about the solutions of this kinds of equations. Where can I find them and read more?

-
By that, am I correct in assuming that you mean all $n$ for which there are $52$ integer pairs $(a,b)$ with $a<b$ such that $2n^2=a^2+b^2$? –  Cameron Buie Aug 22 '12 at 8:14
Or do you perhaps mean $104$ such pairs? –  Cameron Buie Aug 22 '12 at 8:25
@Cameron Buie: Yes, $(a, b)$ and $(b, a)$ are different pairs, so $(n, n)$ is one solution, and then we have $52\cdot 2$ other solutions. –  pts Aug 22 '12 at 9:25

Here is a very closely related question. The formula for the number of solutions is the product of $2m+1$ where $m$ runs through the multiplicities of division of the prime factors of $n$ that are${}\equiv1\pmod4$. So you could take $n=5^{52}$ as one solution to you problem, but you'll get smaller solutions using the factorization $105=3\times5\times7$, the smallest one being $n=5^3\times13^2\times17=359125$. A proof of the result (which uses Gaussian integers) can be found in this answer.

-
Thank you for the answer, it helped me a lot! Could you please be more specific how I generate all $n$s which have 105 solutions? I don't need a proof for that. –  pts Aug 22 '12 at 9:44
The complete list of sets $\{m_1,\ldots,m_k\}$ of integers $m_i>0$ with $(2m_1+1)\ldots(2m_k+1)=105$ is $\{52\},\{17,1\}, \{10,2\}, \{7,3\}, \{3,2,1\}$. Use those as exponents to distinct primes${}\equiv1\pmod4$ and multiply together, and you will generate all positive solutions for $n$. –  Marc van Leeuwen Aug 22 '12 at 10:24
Oops, one omission. You can also throw in any product of primes that are${}\not\equiv1\pmod4$, as such factors do not change the number of solutions (the set of solutions is just uniformly multiplied by the same factor). Only thus will you generate all solutions. –  Marc van Leeuwen Aug 22 '12 at 10:38

You can find a proof in LeVeque's "Fundamentals of Number Theory" of the following fact:

"If $n$ is written as a product $$n = 2^u \times \prod_{p_j\equiv 1 \pmod{4}} p_j^{t_j} \times \prod_{q_j\equiv 3 \pmod{4}} q_j^{s_j}$$ and we write this as $2^un'm$ where $n'$ is the first product and $m$ is the second, then the number of representations of $n$ as a sum of two squares is zero if $m$ is not a square , and $4\tau(n')$ if $m$ is a square. (Where $\tau(n)$ is the the number of positive divisors of $n$.

In my edition (1977), this appears as Theorem 7,6 on page 185.

Note that in the above, the number of representations includes those by squares of negative integers, so that we need to remove the factor 4, if we are considering only representations by positive integers.

Thus we need to find the smallest $k$ such that $\tau(k) = 105$. Using the standard formula for $\tau(k)$, we need $k = p_1^6\times p_2^4 \times p_3^2$ where the primes $p_i \equiv 1 \pmod{4}$.

This should give $k=5^6\times13^4\times 17^2$, which means that your $n$ needs to be $5^3\times 13^2 \times 17 = 359125$

-
But the number of ordered pairs $(a,b)$, which is what OP is asking for, doesn't have to be a multiple of 4. E.g., if $n=1$, then only $(1,1)$ qualifies. –  Gerry Myerson Aug 22 '12 at 8:57
Agreed - deleted part of my answer. –  Old John Aug 22 '12 at 9:06
Thank you for the answer, I learned a lot from it. –  pts Aug 22 '12 at 12:51

Observe that, $a,b$ must be of same parity , else $a^2+b^2$ will be odd.

$=>n^2=(\frac{a+b}{2})^2+(\frac{a-b}{2})^2=p^2+q^2$ for some integer $p,q$

( So, $a+b=±2p$ and $a-b=±2q$ leading to two pairs of $(a,b)$. )

For $n^2$ the factor(which will be in the even power, say $P^2$) of the form $(2^r\prod q_i)^2$ where $q_i≡-1(mod\ 4)$ will have only one form as the sum of squares $0^2+P^2$.

Any number $N$ having $m$ prime factors each ≡1(mod 4) can be expressed $2^{m-1}$ ways.

If ${2u}$ is the highest power of $p_i$ that divides $n^2$ where $p_i$ ≡1(mod 4), the number possible ways of $p_i^{2u}$ can be expressed as a sum of squares is

$u$ if we only allow positive integers,

$2u$ if we allow non-zero integers,

$2u+1$ (1 due to $p_i^{2u}+0^2$) if we allow all integers .

If $n^2=(2^r\prod q_i)^2\prod_{1 ≤i ≤ n} p_i^{2u_i}$, the number possible ways will be $\prod (2u_i+1)$

Look into this, Theorem 3 for details.

-
This relation can easily seen by considering $a^2 + b^2 = (a + ib)(a - ib) = c^2 \Rightarrow ((1 + i)(a + ib))((i - i)(a - ib)) = 2(a + ib)(a - ib) = 2c^2$ –  Lieven Aug 22 '12 at 10:09
I don't understand much of this answer. You seem to be implying the number of pairs $(a,b)$ is always a power of $2$ (which would imply the question as posed has no solution since $105$ is not a power of $2$). That is definitely wrong. –  Marc van Leeuwen Aug 22 '12 at 10:34
@MarcvanLeeuwen, could you please verify? –  lab bhattacharjee Aug 22 '12 at 12:52
@labbhattacharjee: What is there to verify? In fact the number is always odd (since $(n,n)$ is a solution) so powers of $2$ are not a great bet. For $n=125$ you get $7$ solutions $(25,175),(73,161),(85,155),(125,125),(155,85),(161,73),(175,25)$, not anywhere near a power of $2$ (unless you can find one more solution:-). –  Marc van Leeuwen Aug 22 '12 at 13:20
Oh, I see the answer has changed as well, did you want me to verify that added line? The $\prod(u_i+1)$ should be $\prod(2u_i+1)$, which indeed is always odd. –  Marc van Leeuwen Aug 22 '12 at 13:23