Since $(a,b)=1$ then $(ab, a^{2}+b^{2})=1$, so for any $p\leq\sqrt{n}$, $p$ does not divide $n$. So $n$ is a prime. Let $p_{1}=2, \ldots p_{k}\leq sqrt{a^{2}+b^{2}}$ be the prime numbers less than $\sqrt{n}$. So $ab$ is divisible by$p_{1}\cdot p_{2} \ldots p_{k}$, and $ab\geq p_{1}p_{2}\ldots p_{k}$. Suppose $\sqrt{n}\geq 16$. Then using Bertrand, we have that there exista at least one prime number between $\frac{\sqrt{n}}{16}$ and $\frac{\sqrt{n}}{8}$, one prime number between $\frac{\sqrt{n}}{8}$ and $\frac{\sqrt{n}}{4}$, one prime number between $\frac{\sqrt{n}}{4}$ and $\frac{\sqrt{n}}{2}$, and one prime number between $\frac{\sqrt{n}}{2}$ and $\sqrt{n}$. Since $ab$ divides the product of these 4 numbers, then $ab\geq \frac{\sqrt{n}}{8}\cdot\frac{\sqrt{n}}{4}\cdot\frac{\sqrt{n}}{2}\cdot\sqrt{n}=\frac{n^{2}}{1024}$. Well, $ab\leq \frac{a^{2}+b^{2}}{2}=\frac{n}{2}$. So, $\frac{n}{2}\geq\frac{n^{2}}{1024}$, or $n\leq 512$. If $\sqrt{n}\leq 16$ we obtain $n\leq 256$. So treating the case $n\leq 512$ includes $n\leq 256$. It implies $a,b\leq22$. If $n \geq 13^{2}$, then $ab \vdots 13$. Since $a,b\leq 22$, then WLOG (without loss of generality) $a = 13$. Then $22\geq b\vdots 2\cdot3\cdot5\cdot7\cdot11$, impossible. So $n\leq168$. So $a,b\leq12$. If $n\geq 121$, then $ab\vdots 11$. WLOG $a=11$. Then $12\geq b\vdots 2\cdot3\cdot5\cdot7$, impossible. So $n\leq120$. We proceed analogously with the case $n\geq 7^{2}$. We get $n\leq48$. And analogously with casse $n\geq25$. We get $n\leq24$. Since $n$ is a prime, an easy checking gives $n=13$, with $a=2, b=3$. So the only solution is $n=13$.

I use a theorem that there is at least a prime between n and 2n(n>1). But how to prove this one?

Well, this is Bertrand's postulate, and it is fairly hard to prove.. But! look at this wonderful proof due to Erdös : http://en.wikipedia.org/wiki/Proof_of_Bertrand's_postulate .

jin wrote: I use a theorem that there is at least a prime between n and 2n(n>1). But how to prove this one? Revived this old topic because I encountered this problem again and saw that the solution uses Bertrand's postulate unnecessarily. Here is a clean solution without Bertrand's Postulate using only some known facts, and this way we can also remove the constraint $\gcd(a,b)=1$ if one doesn't get bored of tedious work. Let $k$ be the unique positive integer such that $p_k^2\leq n<p_{k+1}^2$ where $p_i$ is the $i$th prime. Since any prime $p\leq\sqrt n$ divides $ab$, we must have $\prod_{i=1}^kp_i|ab$ and thus $ab\geq\prod_{i=1}^kp_i$. From Bonse's Inequality, $\prod_{i=1}^kp_i>p_{k+1}^2$ for $k\geq4$. Thus, using A.M-G.M \[n=a^2+b^2\geq2ab\geq2\prod_{i=1}^kp_i>2p_{k+1}^2>2n\]if $k\geq4$. Thus $k\leq4$ and $\sqrt n<7$ or $n<49$. Also, if $\gcd(a,b)=1$, no prime of the form $4k+3$ divides $a^2+b^2$. Otherwise, $\dfrac{p-1}2$ is odd, so $p|(a^2)^{\frac{p-1}2}+(b^2)^{\frac{p-1}2}=a^{p-1}+b^{p-1}$. But from Fermat's Little Theorem, $p|1+1=2$, contradiction. Thus $n$ has only prime factor $2,5,13,17,29,37,41$. Let's consider two cases. If $n$ is prime, then $n=2,5,13$ are valid according to the statement. $17=4^2+1,29=2^2+5^2,37=6^2+1,41=4^2+5^2$ and in no representation $ab$ is divisible by $3$. Now, $n$ is composite. Notice that $n$ can not have prime factor greater than $17$ since $29\cdot2=58>49$. If $13$ divides $n$, then $n$ must be $2\cdot13$ since $3$ doesn't divide $n$ and $4\cdot13=52>49$. But $26=5^2+1$, doesn't follow the rules. Similarly, if $17$ divides $n$ then $n=34=5^2+3^2$ but same problem. If $2$ divides $n$, then $4$ can not divide $n$. Because then $a$ and $b$ both have to be even. Therefore $n$ must be $10=1^2+3^2$ but this is not possible either. If $5$ divides $n$ then $n$ must be $25=3^2+4^2$ which is not valid either. Thus, $n=\boxed{2,5,13}$ are all solutions.

WLOG $1 \leq b \leq a$.

a-b=0

a-b=1

a-b>1

answer

Since $p \le \sqrt{n}$ and $\gcd(a,b)=1$ either $p|a$ or $p|b$ Since $(a,b)=1$ then $(ab, a^{2}+b^{2})=1$, so for any $p\leq\sqrt{n}$, $p$ does not divide $n$. So $n$ is a prime and $\equiv 1 \pmod 4$(other than $n=2$ of course) Denote $p_1,p_2,p_3....$ be the primes less than $\sqrt{n}$ Using Bonse's inequality yeilds $ab \ge \prod{p_k}>p_{k+1}^2>$,a contradiction so $k \le 3$ and $\sqrt{n}<7$ $n \ge 24$ is ruled out by size arguments and checking all remaining possibilities gives $n=[2,5,13]$