Maths Olympiad Prep

Library / /578 of 740

, 2018

Number theory Difficulty 5.3 AIME, harder Prove it United States

Problem:

A positive integer is called primer if it has a prime number of distinct prime factors. A positive integer is called primest if it has a primer number of distinct primer factors. Find the smallest primest number.

Solution

Solution:

We claim the answer is 7272, as it has 66 primer factors: 6,12,24,18,36,726, 12, 24, 18, 36, 72, and 66 is a primer.

We now prove that there is no smaller primest number. Suppose there were a smaller primest number r<72r < 72. We do casework on the number of distinct prime factors of rr.

- rr has 4\geq 4 distinct prime factors. Then r2357=210r \geq 2 \cdot 3 \cdot 5 \cdot 7 = 210, which is larger than 7272.

- rr has 33 distinct prime factors. If each of these factors has multiplicity 11, i.e. r=pqsr = p q s for distinct primes p,q,sp, q, s, then rr has precisely 44 primer factors: pq,qs,sp,pqsp q, q s, s p, p q s, and 44 is not a primer. Thus, rr contains at least one factor of multiplicity at least 22. If rr is p2qsp^{2} q s for distinct primes p,q,sp, q, s, then rr has 77 distinct primer factors: pq,qs,sp,pqs,p2q,sp2,p2qsp q, q s, s p, p q s, p^{2} q, s p^{2}, p^{2} q s, and 77 is not a primer. Thus, if r=paqbscr = p^{a} q^{b} s^{c}, a+b+c5a + b + c \geq 5, and r2335=120r \geq 2^{3} \cdot 3 \cdot 5 = 120, which is 72\geq 72.

- rr has 22 distinct prime factors. If r=paqbr = p^{a} q^{b}, for distinct primes p,qp, q, then rr's primer factors are precisely its divisors of the form piqjp^{i} q^{j}, where 1ia1 \leq i \leq a and 1jb1 \leq j \leq b, meaning that it has aba b primer factors. Thus, aba b is a primer, meaning that ab6a b \geq 6. Thus r2332=72r \geq 2^{3} \cdot 3^{2} = 72, where the other possibilities can be ruled out through easy casework.

- rr has 11 distinct prime factor. Then it doesn't have any primer factors, and thus cannot possibly have a primer number of them.

We conclude that 7272 is the smallest primest number.

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.