Maths Olympiad Prep

Library / /52 of 94

Number theory Difficulty 6.2 National Olympiad Prove it Hong Kong

For any positive integer nn, let a1,a2,,ama_1, a_2, \dots, a_m be all the positive divisors of nn, where m1m \ge 1. If there exist mm integers b1,b2,,bmb_1, b_2, \dots, b_m such that n=i=1m(1)biain = \sum_{i=1}^{m} (-1)^{b_i} a_i, then we say that nn is a good number. Prove that there exists a good number with exactly 2013 distinct prime factors.

Solution

We say that a positive integer nn is excellent if it is good, and we can find integers c1,c2,,cmc_1, c_2, \dots, c_m such that j=1m(1)cjaj=0\sum_{j=1}^{m} (-1)^{c_j} a_j = 0. Let p1,p2,,pkp_1, p_2, \dots, p_k be distinct primes larger than 3. We prove by induction on kk that the integer 6p1p2pk6p_1p_2\cdots p_k is excellent.

For the base case k=0k=0, the positive divisors of 66 are 11, 22, 33, 66. Since we have 12+3+6=6-1-2+3+6=6 and 123+6=0-1-2-3+6=0, the integer 66 is excellent.

For the inductive step, assume n=6p1p2pkn = 6p_1p_2\cdots p_k is excellent. Let a1,a2,,ama_1, a_2, \dots, a_m be all of its positive divisors, and let
j=1m(1)bjaj=nandj=1m(1)cjaj=0. \sum_{j=1}^{m} (-1)^{b_j} a_j = n \quad \text{and} \quad \sum_{j=1}^{m} (-1)^{c_j} a_j = 0.
Consider n=6p1p2pk+1n' = 6p_1p_2\cdots p_{k+1}. Its positive divisors are of the form aja_j and ajpk+1a_jp_{k+1}. Note that
j=1m(1)cjaj+j=1m(1)bj(ajpk+1)=0+npk+1=n. \sum_{j=1}^{m} (-1)^{c_j} a_j + \sum_{j=1}^{m} (-1)^{b_j} (a_j p_{k+1}) = 0 + n p_{k+1} = n'.
Also, we have
j=1m(1)cjaj+j=1m(1)bj(ajpk+1)=0+0pk+1=0. \sum_{j=1}^{m} (-1)^{c_j} a_j + \sum_{j=1}^{m} (-1)^{b_j} (a_j p_{k+1}) = 0 + 0 \cdot p_{k+1} = 0.
Therefore, nn' is excellent. By induction, our claim holds. In particular, we can take k=2011k=2011 so that 6p1p2p20116p_1p_2\cdots p_{2011} is excellent, and hence it is a good integer with exactly 2013 prime divisors.

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.