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 2 of 4: Force consecutive summands

Previous step Next step

a-b>1; p | (a-b); p <= a-b < sqrt(a^2+b^2)=sqrt(n)

Detailed analysis

Suppose $a>b$ and $a-b>1$ . Choose a prime divisor $p$ of $a-b$ . Since $p<=a-b<sqrt(a^2+b^2)=sqrt(n)$ , the hypothesis gives $p | ab$ . Thus $p$ divides $a$ or $b$ ; together with $p | (a-b)$ this makes $p$ divide both, contradicting $gcd(a,b)=1$ . Hence $a-b=1$ .