Maths Olympiad Prep

Library / /12 of 19

, 2021

Number theory Difficulty 5.2 AIME, harder Prove it United States

Problem:
Compute the product of all positive integers b2b \geq 2 for which the base bb number 111111b111111_{b} has exactly bb distinct prime divisors.

Solution

Solution:
Notice that this value, in base bb, is
b61b1=(b+1)(b2b+1)(b2+b+1) \frac{b^{6}-1}{b-1} = (b+1)\left(b^{2}-b+1\right)\left(b^{2}+b+1\right)
This means that, if bb satisfies the problem condition, (b+1)(b2b+1)(b2+b+1)(b+1)\left(b^{2}-b+1\right)\left(b^{2}+b+1\right) has more than p1pbp_{1} \ldots p_{b}, where pip_{i} is the iith smallest prime.
We claim that, if b7b \geq 7, then p1pb>(b+1)(b2b+1)(b2+b+1)p_{1} \ldots p_{b} > (b+1)\left(b^{2}-b+1\right)\left(b^{2}+b+1\right). This is true for b=7b=7 by calculation, and can be proven for larger bb by induction and the estimate piip_{i} \geq i.
All we have to do is to check b2,3,4,5,6b \in 2,3,4,5,6. Notice that for b=6b=6, the primes cannot include 2,32,3 and hence we want 6615\frac{6^{6}-1}{5} to be divisible by a product of 6 primes the smallest of which is 5. However, 5717>66155 \cdot 7 \cdots 17 > \frac{6^{6}-1}{5}, and by checking we rule out 5 too. All that is left is {2,3,4}\{2,3,4\}, all of which work, giving us an answer of 24.

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.