MathLabs

第3题

求所有能写成 n=a2+b2n=a^2+b^2 的正整数 nn,其中 a,ba,b 是互素正整数,且每个满足 p<=sqrt(n)p <= sqrt(n) 的素数都整除 abab。
第 3/4 步:限制较小的加数
a=b+1;b<=2a=b+1; b<=2
详细分析

令 a=b+1a=b+1。当 b−1>1b-1>1 时,b−1b-1 的任一素因数 pp 都满足 p<=b−1<sqrt(n)p<=b-1<sqrt(n),因而整除 b(b+1)b(b+1)。它不可能整除 bb,所以必须整除 b+1b+1,进而整除 22;故 b−1b-1 的素因数只能是 22。若 b>=3b>=3,则 bb 为奇数且 b+2<=sqrt(2b2+2b+1)=sqrt(n)b+2<=sqrt(2b^2+2b+1)=sqrt(n)。b+2b+2 的素因数应整除 b(b+1)b(b+1),但 gcd(b+2,b)=gcd(b+2,b+1)=1gcd(b+2,b)=gcd(b+2,b+1)=1,不可能。因此 b<=2b<=2。