Maths Olympiad Prep

Library / /117 of 860

Number theory Difficulty 4.8 AIME Find the answer

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

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

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)>p1pb(b+1)\left(b^{2}-b+1\right)\left(b^{2}+b+1\right)>p_{1} \ldots p_{b}, where pip_{i} is the ii th 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,3 and hence we want 6615\frac{6^{6}-1}{5} to be divisible 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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.