Maths Olympiad Prep

Library / /17 of 26

, 1994

Number theory Difficulty 7.7 National Olympiad, round 2 Prove it Asia Pacific Mathematics Olympiad (APMO)

Let nn be an integer of the form a2+b2a^{2}+b^{2}, where aa and bb are relatively prime integers and such that if pp is a prime, pnp \leq \sqrt{n}, then pp divides aba b. Determine all such nn.

Answer: n=2,5,13n=2,5,13.

Solution

A prime pp divides aba b if and only if divides either aa or bb. If n=a2+b2n=a^{2}+b^{2} is a composite then it has a prime divisor pnp \leq \sqrt{n}, and if pp divides aa it divides bb and vice-versa, which is not possible because aa and bb are coprime. Therefore nn is a prime.

Suppose without loss of generality that aba \geq b and consider aba-b. Note that a2+b2=(ab)2+2aba^{2}+b^{2}=(a-b)^{2}+2 a b.

- If a=ba=b then a=b=1a=b=1 because aa and bb are coprime. n=2n=2 is a solution.

- If ab=1a-b=1 then aa and bb are coprime and a2+b2=(ab)2+2ab=2ab+1=2b(b+1)+1=2b2+2b+1a^{2}+b^{2}=(a-b)^{2}+2 a b=2 a b+1=2 b(b+1)+1= 2 b^{2}+2 b+1. So any prime factor of any number smaller than 2b2+2b+1\sqrt{2 b^{2}+2 b+1} is a divisor of ab=b(b+1)a b=b(b+1).

One can check that b=1b=1 and b=2b=2 yields the solutions n=12+22=5n=1^{2}+2^{2}=5 (the only prime pp is 2) and n=22+32=13n=2^{2}+3^{2}=13 (the only primes pp are 2 and 3). Suppose that b>2b>2.

Consider, for instance, the prime factors of b12b2+2b+1b-1 \leq \sqrt{2 b^{2}+2 b+1}, which is coprime with bb. Any prime must then divide a=b+1a=b+1. Then it divides (b+1)(b1)=2(b+1)-(b-1)=2, that is, b1b-1 can only have 2 as a prime factor, that is, b1b-1 is a power of 2 , and since b12b-1 \geq 2, bb is odd.

Since 2b2+2b+1(b+2)2=b22b3=(b3)(b+1)02 b^{2}+2 b+1-(b+2)^{2}=b^{2}-2 b-3=(b-3)(b+1) \geq 0, we can also consider any prime divisor of b+2b+2. Since bb is odd, bb and b+2b+2 are also coprime, so any prime divisor of b+2b+2 must divide a=b+1a=b+1. But b+1b+1 and b+2b+2 are also coprime, so there can be no such primes. This is a contradiction, and b3b \geq 3 does not yield any solutions.

- If ab>1a-b>1, consider a prime divisor pp of ab=a22ab+b2<a2+b2a-b=\sqrt{a^{2}-2 a b+b^{2}}<\sqrt{a^{2}+b^{2}}. Since pp divides one of aa and b,pb, p divides both numbers (just add or subtract aba-b accordingly.) This is a contradiction.

Hence the only solutions are n=2,5,13n=2,5,13.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.