Problem 3

Find all positive integers

n

that can be written as

n=a^2+b^2

, where

a,b

are relatively prime positive integers and every prime

p <= sqrt(n)

divides

ab

Step 4 of 4: Check the remaining cases

Previous step Next step

(a,b)=(1,1),(2,1),(3,2); n=2,5,13

Detailed analysis

If $a>b$ , then $a=b+1$ and $b=1$ or $2$ , giving $(a,b)=(2,1)$ or $(3,2)$ and hence $n=5$ or $13$ . Their required primes are respectively $2$ , and $2,3$ , all of which divide $ab$ . Together with $(1,1)$ , the complete answer is $n=2,5,13$ .