Maths Olympiad Prep

Library / /21 of 28

, 2024

Number theory Difficulty 5.6 AIME, harder Prove it United States

Problem:

An ordered pair (a,b)(a, b) of positive integers is called spicy if gcd(a+b,ab+1)=1\operatorname{gcd}(a+b, a b+1)=1. Compute the probability that both (99,n)(99, n) and (101,n)(101, n) are spicy when nn is chosen from {1,2,,2024!}\{1,2, \ldots, 2024!\} uniformly at random.

Solution

Solution:

We claim that (a,b)(a, b) is spicy if and only if both gcd(a+1,b1)=1\operatorname{gcd}(a+1, b-1)=1 and gcd(a1,b+1)=1\operatorname{gcd}(a-1, b+1)=1.

To prove the claim, we note that
gcd(a+b,ab+1)=gcd(a+b,b(b)+1)=gcd(a+b,b21) \operatorname{gcd}(a+b, a b+1)=\operatorname{gcd}(a+b, b(-b)+1)=\operatorname{gcd}\left(a+b, b^{2}-1\right)
Hence, we have
gcd(a+b,ab+1)=1gcd(a+b,b21)=1gcd(a+b,b1)=1 and gcd(a+b,b+1)=1gcd(a+1,b1)=1 and gcd(a1,b+1)=1, \begin{aligned} \operatorname{gcd}(a+b, a b+1)=1 & \Longleftrightarrow \operatorname{gcd}\left(a+b, b^{2}-1\right)=1 \\ & \Longleftrightarrow \operatorname{gcd}(a+b, b-1)=1 \text{ and } \operatorname{gcd}(a+b, b+1)=1 \\ & \Longleftrightarrow \operatorname{gcd}(a+1, b-1)=1 \text{ and } \operatorname{gcd}(a-1, b+1)=1, \end{aligned}
proving the claim.

Thus, nn works if and only if all following four conditions hold:
- gcd(n+1,98)=1\operatorname{gcd}(n+1,98)=1, or equivalently, nn is neither 1(mod2)-1\pmod{2} nor 1(mod7)-1\pmod{7};
- gcd(n1,100)=1\operatorname{gcd}(n-1,100)=1, or equivalently, nn is neither 1(mod2)1\pmod{2} nor 1(mod5)1\pmod{5};
- gcd(n+1,100)=1\operatorname{gcd}(n+1,100)=1, or equivalently, nn is neither 1(mod2)-1\pmod{2} nor 1(mod5)-1\pmod{5}; and
- gcd(n1,102)=1\operatorname{gcd}(n-1,102)=1, or equivalently, nn is neither 1(mod2)1\pmod{2}, 1(mod3)1\pmod{3}, nor 1(mod17)1\pmod{17}.

Thus, there are 1,2,3,6,171,2,3,6,17 possible residues modulo 2,3,5,72,3,5,7, and 1717, respectively. The residues are uniformly distributed within {1,2,,2024!}\{1,2, \ldots, 2024!\}. Hence, the answer is
122335671617=96595 \frac{1}{2} \cdot \frac{2}{3} \cdot \frac{3}{5} \cdot \frac{6}{7} \cdot \frac{16}{17} = \frac{96}{595}

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.