Library / Brazilian Math Olympiad /9 of 66

Brazilian Math Olympiad

Number theory Difficulty 4.7 AIME Prove it Brazil

Let $P(n)$ be a polynomial with real coefficients. Prove that there exist integers $n$ and $k$ such that $k$ has at most $n$ digits and at least $P(n)$ divisors.

Solution

Let $d$ be the degree of $P$ , and consider $d+1$ distinct primes $p_1, p_2, \dots, p_{d+1}$ . Let $A = p_1p_2\dots p_{d+1}$ and $k_N = A^N$ . If $A$ has $r$ digits, then $k_N$ has at most $rN$ digits. On the other hand, $k_N$ has $(N+1)^{d+1}$ positive divisors. Since $P$ has degree $d$ , $P(rN) < (N+1)^{d+1}$ for all sufficiently large $N$ , which solves the problem.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.