(HMMT 2000 Guts Round #27). Find the smallest positive integer that can be written as a sum of two squares in exactly three different ways.
By using a computer program, I found the number $325.$ It can only be written as $15^2 + 10^2, 1^2+18^2,6^2+17^2.$ One can verify this by observing that if $a^2 + b^2 = 325,$ then we may assume WLOG that $a\leq b$ so that $2a^2 \leq 325\Rightarrow a \leq 12.$ Thus it suffices to find the values of a that are at most 12 and such that $325-a^2$ is a perfect square. It could be useful to list the first few perfect squares: $0,1,4,9,16,25,36,49,64,81,100,121,144,169,196,225,256,289,324.$ Now suppose for a contradiction that some number that's at most $324$ can be expressed as a sum of two squares in three different ways. Note that all the perfect squares listed can be expressed as a sum of two squares in at most two different ways. I know that if $x^2 + y^2=z^2$ is a primitive Pythagorean triple of positive integers with x odd, then there exists integers $u>v>0$ of different parity so that $x=u^2-v^2, y = 2uv, z=u^2+v^2$. So one could use this theorem to find some primitive Pythagorean triples with $z\leq 18$. For instance, we can choose $u=3,v=2$ to get $x=5, y=12,z=13$. By checking values of $v$ that are at most 2, we see that the only other primitive triples with $z\leq 18$ are $(x,y,z) = (15,8,17)$ and $(3,4,5).$ Thus since any Pythagorean triple is a "multiple" of a primitive triple, the only Pythagorean triples with $z\leq 18$ are $(3,4,5),(9,12,15), (5,12,13),(15,8,17).$ Each value of $z$ leads to a unique pair $(x,y)$ and so the claim that all perfect squares that are at most 324 can only be expressed as the sum of two squares in at most 2 ways holds. So we just need to consider non-perfect squares, though I'm not sure of an approach that isn't computationally intensive.
Best Answer
Let $n$ be the smallest integer that can be written as a sum of two squares in exactly three different ways. Then $$n=x_1^2+x_2^2=x_3^2+x_4^2=x_5^2+x_6^2,$$ for some nonnegative integers $x_i$. Consider the prime factorization of $n$:
If $n$ is divisible by a prime $p\equiv3\pmod{4}$, then also the $x_i$ are all divisible by $p$. But then dividing the $x_i$ by $p$ shows that $\frac{n}{p^2}$ is a sum of two squares in exactly three different ways, contradicting the minimality of $n$.
Similarly, if $n$ is divisible by $4$ then reducing mod $4$ shows that all the $x_i$ are even. But then dividing the $x_i$ by $2$ shows that $\frac{n}{4}$ is a sum of two squares in exactly three different ways, contradicting the minimality of $n$.
If $n\equiv2\pmod{4}$ then reducing mod $4$ shows that all the $x_i$ are odd. But then the identity $$\left(\frac{x_1+x_2}{2}\right)^2+\left(\frac{x_1-x_2}{2}\right)^2=\frac{x_1^2+x_2^2}{2}=\frac{n}{2},$$ shows that $\frac{n}{2}$ is a sum of two squares in exactly three different ways, contradicting the minimality of $n$.
This shows that all prime factors of $n$ are congruent to $1$ modulo $4$. Of course if $n$ is prime then it can be written as a sum of squares in only one way. If $n$ is a product of two primes then it can be written as a sum of squares in at most two ways. So $n$ must be a product of at least three primes congruent to $1$ mod $4$.
The smallest such number is $5^3=125$. If $125=x_i^2+x_j^2$ with $x_i>x_j$ then $x_i\geq8$ and of course $x_i\leq11$. It is then easy to check that $125$ can not be written as a sum of two squares in exactly three ways.
The next such number is $5^2\times13=325$. If $325=x_i^2+x_j^2$ with $x_i>x_j$ then $x_i\geq13$, and of course $x_i\leq18$. It is then easy to check that $325$ can be written as a sum of two squares in exactly three ways.