Maths Olympiad Prep

Library / /14 of 18

Number theory Difficulty 4.2 AIME Prove it North Macedonia

Find all positive integers nn such that nn has number of ciphers which is the same as the number of its different prime divisors and the sum of the different prime divisors is equal to the sum of their powers.

Solution

Let n=p1a1p2a2pkakn = p_1^{a_1}p_2^{a_2}\ldots p_k^{a_k}. From the condition of the problem
p1+p2++pk=a1+a2++ak. p_1 + p_2 + \ldots + p_k = a_1 + a_2 + \ldots + a_k.
We discuss the number of ciphers of the number nn. If nn has 4 ciphers, then he has 4 different prime divisors. Then n214357>104n \ge 2^{14} \cdot 3 \cdot 5 \cdot 7 > 10^4 which is not possible. If nn has k>4k > 4 ciphers, then
n222+3+5+7++p5++pk(k1)357p5pk=2143572p5++pk(k1)p5pk>10410k1=10k n \ge 2^{22+3+5+7+\ldots+p_5+\ldots+p_k-(k-1)} \cdot 3 \cdot 5 \cdot 7 \cdot p_5 \dots p_k = 2^{14} \cdot 3 \cdot 5 \cdot 7 \cdot 2^{p_5+\ldots+p_k-(k-1)} \cdot p_5 \dots p_k \\ > 10^4 \cdot 10^{k-1} = 10^k
which again is not possible.
So, we get that nn has at least three ciphers.
Let nn have three ciphers. Then n=p1a1p2a2p3a3n = p_1^{a_1}p_2^{a_2}p_3^{a_3}. If 5n5|n, then n2835>103n \ge 2^8 \cdot 3 \cdot 5 > 10^3.
We get that the prime divisors of the number nn are 3\le 3. But, prime numbers 3\le 3 are 2 and 3, and in the factorization of the number nn there are 3 prime numbers, which is a contradiction.
Let nn has two ciphers. Then n=p1a1p2a2n = p_1^{a_1}p_2^{a_2}. If 5n5|n, then n265>102n \ge 2^6 \cdot 5 > 10^2. Remains n=2a13a2n = 2^{a_1}3^{a_2} where a1+a2=5a_1 + a_2 = 5. With direct checking we get that n=243=48,n=2332=72n = 2^4 \cdot 3 = 48, n = 2^3 \cdot 3^2 = 72 are solutions of the problem.
Let nn has one cipher. Then only n=22n = 2^2 fulfils the condition of the problem.

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.