Maths Olympiad Prep

Library / /564 of 740

, 2024

Number theory Difficulty 5.2 AIME, harder Prove it United States

Problem:
Suppose that aa and bb are positive integers such that gcd(a3b3,(ab)3)\operatorname{gcd}\left(a^{3}-b^{3},(a-b)^{3}\right) is not divisible by any perfect square except 1. Given that 1ab501 \leq a-b \leq 50, compute the number of possible values of aba-b across all such a,ba, b.

Solution

Solution:
Claim 1. Let aa and bb be positive integers. Then, gcd(a3b3,(ab)3)\operatorname{gcd}\left(a^{3}-b^{3},(a-b)^{3}\right) is squarefree if and only if gcd(a,b)=1\operatorname{gcd}(a, b)=1, aba-b is squarefree, and aba-b is not divisible by 3.

Proof. If gcd(a,b)=d>1\operatorname{gcd}(a, b)=d>1, then gg is divisible by d3d^{3}, hence not squarefree. Thus, we now restrict our attention to the case gcd(a,b)=1\operatorname{gcd}(a, b)=1. In that case, we factor out aba-b from the gcd and simplify it as follows:
gcd(a3b3,(ab)3)=(ab)gcd(a2+ab+b2,(ab)2)=(ab)gcd((ab)2+3ab,(ab)2)=(ab)gcd((ab)2,3ab) \begin{aligned} \operatorname{gcd}\left(a^{3}-b^{3},(a-b)^{3}\right) & =(a-b) \operatorname{gcd}\left(a^{2}+a b+b^{2},(a-b)^{2}\right) \\ & =(a-b) \operatorname{gcd}\left((a-b)^{2}+3 a b,(a-b)^{2}\right) \\ & =(a-b) \operatorname{gcd}\left((a-b)^{2}, 3 a b\right) \end{aligned}
Moreover, since gcd(a,b)=1\operatorname{gcd}(a, b)=1, we have that gcd(ab,a)=gcd(ab,b)=1\operatorname{gcd}(a-b, a)=\operatorname{gcd}(a-b, b)=1, and so gcd((ab)2,ab)=1\operatorname{gcd}\left((a-b)^{2}, a b\right)=1, which implies that gcd((ab)2,3ab)\operatorname{gcd}\left((a-b)^{2}, 3 a b\right) is either 1 or 3.

Thus, each of the following is equivalent to the next.
- gcd(a3b3,(ab)3)\operatorname{gcd}\left(a^{3}-b^{3},(a-b)^{3}\right) is squarefree.
- (ab)gcd((ab)2,3ab)(a-b) \operatorname{gcd}\left((a-b)^{2}, 3 a b\right) is squarefree.
- aba-b is squarefree and at least one of aba-b and gcd((ab)2,3ab)\operatorname{gcd}\left((a-b)^{2}, 3 a b\right) is not divisible by 3.
- aba-b is squarefree and aba-b is not divisible by 3.

The claim implies that c=abc=a-b is possible only if cc is squarefree and not divisible by 3. For any such cc, we may construct (a,b)(a, b) that works by taking a=c+1a=c+1 and b=1b=1. Hence, the answer is simply the number of squarefree integers up to 50 that are not divisible by 3.

There are 16 multiples of 3 from 1 to 50. Among the remaining numbers, 4,8,16,20,28,32,40,44,25,504,8,16,20,28,32,40,44,25,50, and 4949 are not squarefree. This leaves 501611=2350-16-11=23 possible values of aba-b.

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.