Maths Olympiad Prep

Library / /7 of 30

Number theory Difficulty 5.5 AIME, harder Find the answer

Find the greatest positive integer xx such that 236+x23^{6+x} divides 2000!2000!

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

Solution

To find the greatest positive integer x x such that 236+x 23^{6+x} divides 2000! 2000! , we need to determine how many times the prime factor 23 appears in the prime factorization of 2000! 2000! .

The exponent of a prime p p in n! n! is given by:
k=1npk \sum_{k=1}^{\infty} \left\lfloor \frac{n}{p^k} \right\rfloor
In this case, n=2000 n = 2000 and p=23 p = 23 .

Let's calculate each term until we reach a power where the division results in a number less than 1:

1. 200023=86.95652=86\left\lfloor \frac{2000}{23} \right\rfloor = \left\lfloor 86.95652 \right\rfloor = 86

2. 2000232=2000529=3.78337=3\left\lfloor \frac{2000}{23^2} \right\rfloor = \left\lfloor \frac{2000}{529} \right\rfloor = \left\lfloor 3.78337 \right\rfloor = 3

3. 2000233=200012167=0.16438=0\left\lfloor \frac{2000}{23^3} \right\rfloor = \left\lfloor \frac{2000}{12167} \right\rfloor = \left\lfloor 0.16438 \right\rfloor = 0

For higher powers of 23, such as 234 23^4 , the floor function results in 0, since 234=279841 23^4 = 279841 is greater than 2000.

Therefore, the total number of times 23 appears as a factor in 2000! 2000! is:
86+3+0=89 86 + 3 + 0 = 89

We want 236+x 23^{6+x} to divide 2000! 2000! , so we set:
6+x89 6 + x \leq 89
Solving for x x , we get:
x83 x \leq 83

Therefore, the greatest positive integer x x is:
83 \boxed{83}

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.