Maths Olympiad Prep

Library / /55 of 520

Number theory Difficulty 6.4 National olympiad Find the answer

Let p1,p2,p3,p4p_1,p_2,p_3,p_4 be four distinct primes, and let 1=d1<d2<<d16=n1=d_1<d_2<\ldots<d_{16}=n be the divisors of n=p1p2p3p4n=p_1p_2p_3p_4. Determine all n<2001n<2001 with the property that
d9d8=22d_9-d_8=22.

A number or a short expression. Spacing and $ signs are ignored.

Solution

1. We are given four distinct primes p1,p2,p3,p4 p_1, p_2, p_3, p_4 such that p1<p2<p3<p4 p_1 < p_2 < p_3 < p_4 and n=p1p2p3p4 n = p_1 p_2 p_3 p_4 . We need to find all n<2001 n < 2001 such that d9d8=22 d_9 - d_8 = 22 , where 1=d1<d2<<d16=n 1 = d_1 < d_2 < \cdots < d_{16} = n are the divisors of n n .

2. Since did17i=n d_i \cdot d_{17-i} = n for all 1i16 1 \leq i \leq 16 , choosing i=8 i = 8 gives us d8d9=n d_8 \cdot d_9 = n .

3. Assume q{2,11} q \in \{2, 11\} and qn q \mid n . Then qd8d9 q \mid d_8 d_9 implies qd8 q \mid d_8 and qd9 q \mid d_9 , leading to q2n q^2 \mid n . However, since n n is square-free, this is impossible. Therefore, p12 p_1 \neq 2 and pi11 p_i \neq 11 for i{2,3,4} i \in \{2, 3, 4\} .

4. Assume p1>3 p_1 > 3 . Then n=p1p2p3p4571317=7735>2000 n = p_1 p_2 p_3 p_4 \leq 5 \cdot 7 \cdot 13 \cdot 17 = 7735 > 2000 , which is a contradiction. Hence, p13 p_1 \leq 3 . Since p22 p_2 \neq 2 , we have p1=3 p_1 = 3 .

5. Assume p2>5 p_2 > 5 . Then p4=np1p2p320003713=2000273<8 p_4 = \frac{n}{p_1 p_2 p_3} \leq \frac{2000}{3 \cdot 7 \cdot 13} = \frac{2000}{273} < 8 , contradicting p4>11 p_4 > 11 . Hence, p25 p_2 \leq 5 , which means p2=5 p_2 = 5 .

6. Given p1=3 p_1 = 3 and p2=5 p_2 = 5 , we have p32<p3p4=n35=n15200015<144=122 p_3^2 < p_3 p_4 = \frac{n}{3 \cdot 5} = \frac{n}{15} \leq \frac{2000}{15} < 144 = 12^2 , yielding p3<12 p_3 < 12 . Therefore, p3=7 p_3 = 7 .

7. Thus, n=357p4=105p4 n = 3 \cdot 5 \cdot 7 \cdot p_4 = 105 p_4 . This implies 105p42000 105 p_4 \leq 2000 , so p42000105<20 p_4 \leq \frac{2000}{105} < 20 . Since p3=7<p419 p_3 = 7 < p_4 \leq 19 and p411 p_4 \neq 11 , we have p4{13,17,19} p_4 \in \{13, 17, 19\} .

8. Since d8d9=n d_8 d_9 = n and n n is odd, d8 d_8 must be odd. Given d9d8=22 d_9 - d_8 = 22 , we have d8d9d82=22d8 d_8 d_9 - d_8^2 = 22 d_8 , leading to d82+22d8=n d_8^2 + 22 d_8 = n . Thus, (d8+11)2=105p4+121 (d_8 + 11)^2 = 105 p_4 + 121 .

9. Since d8 d_8 is odd, 4105p4+121 4 \mid 105 p_4 + 121 , implying 4p4+1 4 \mid p_4 + 1 . Given p4{13,17,19} p_4 \in \{13, 17, 19\} , we find p4=19 p_4 = 19 .

10. Therefore, n=10519=1995 n = 105 \cdot 19 = 1995 . This means d8=57=35 d_8 = 5 \cdot 7 = 35 and d9=319=57 d_9 = 3 \cdot 19 = 57 , yielding d9d8=5735=22 d_9 - d_8 = 57 - 35 = 22 .

The final answer is n=1995 \boxed{ n = 1995 } .

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.