1983 AIME Problem 8

Attempt Problem 8 of the 1983 AIME below, then check your answer against the professionally curated solution from LIVE by Po-Shen Loh. You can also try the full timed exam, view all 1983 AIME solutions, or check the answer key.

All problems are used with official legal permission of the Mathematical Association of America (MAA).

8.

What is the largest 22-digit prime factor of the integer n=(200100)?n=\binom{200}{100}?

Answer: 61
Concepts:Legendre’s Formulaprimeprime factorization
Difficulty rating: 2440
Small Hint:

For a prime p>50,p>50, compare the exponent of pp in 200!200! with twice its exponent in 100!100!

Big Hint:

Primes from 6767 through 9999 cancel; primes from 5151 through 6666 do not

Solution:

For a prime p>50,p>50, we have p2>200,p^2>200, so vp((200100))=200p2100p. \begin{aligned} v_p\left(\binom{200}{100}\right) &=\left\lfloor\frac{200}{p}\right\rfloor\\ &\quad-2\left\lfloor\frac{100}{p}\right\rfloor. \end{aligned} If 67p<100,67\leq p<100, this is 22=0.2-2=0. If 50<p66,50<p\leq66, it is 32=1.3-2=1. Hence no prime greater than 6666 divides the binomial coefficient, while every prime between 5050 and 6666 does. The largest such prime is 61.61.

← Problem 7#7
Full Exam

Problem 8 in Other Years