2016 AIME I Problem 12

Attempt Problem 12 of the 2016 AIME I 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 2016 AIME I solutions, or check the answer key.

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

12.

Find the least positive integer mm such that m2m+11m^2 - m + 11 is a product of at least four not necessarily distinct primes.

Answer: 132
Concepts:prime factorizationmodular arithmeticbounding to limit cases
Difficulty rating: 3160
Solution:

Let e(m)=m2m+11.e(m) = m^2 - m + 11. Since m2mm^2 - m is always even, e(m)e(m) is odd. Checking all residues shows m2m+11m^2 - m + 11 is never 00 modulo 3,3, 5,5, or 77 either, so every prime factor of e(m)e(m) is at least 11.11. A product of four such primes is at least 114=14641,11^4 = 14641, and the two smallest candidates are 11411^4 and 11313=17303.11^3 \cdot 13 = 17303.

For e(m)=14641,e(m) = 14641, the discriminant of m2m14630=0m^2 - m - 14630 = 0 is 58521,58521, which lies strictly between 2412=58081241^2 = 58081 and 2422=58564,242^2 = 58564, so there is no integer solution. For e(m)=17303:e(m) = 17303: since e(m)=m(m1)+11e(m) = m(m - 1) + 11 must be divisible by 11,11, either m=11km = 11k or m=11k+1.m = 11k + 1. Trying m=11km = 11k gives 11k2k+1=1573,11k^2 - k + 1 = 1573, that is k(11k1)=1572,k(11k - 1) = 1572, which k=12k = 12 satisfies: 12131=1572.12 \cdot 131 = 1572.

Since ee is increasing for m1,m \ge 1, every smaller mm has e(m)<17303,e(m) \lt 17303, and the only four-prime value below that, 114,11^4, is unattainable. Hence the least mm is 1112=132,11 \cdot 12 = 132, where e(132)=17303=11313.e(132) = 17303 = 11^3 \cdot 13.

← Problem 11#11
Full Exam

Problem 12 in Other Years