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 3 of 4: Restrict the smaller summand

Previous step Next step

a=b+1; b<=2

Detailed analysis

Write $a=b+1$ . Any prime divisor $p$ of $b-1$ , when $b-1>1$ , satisfies $p<=b-1<sqrt(n)$ and therefore divides $b(b+1)$ . It cannot divide $b$ , so it divides $b+1$ and hence $2$ ; thus $b-1$ has no prime divisor other than $2$ . If $b>=3$ , then $b$ is odd and $b+2<=sqrt(2b^2+2b+1)=sqrt(n)$ . A prime divisor of $b+2$ must divide $b(b+1)$ , but $gcd(b+2,b)=gcd(b+2,b+1)=1$ , impossible. Hence $b<=2$ .