2016 AIME I Problem 12

Below is the professionally curated solution for Problem 12 of the 2016 AIME I, 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 of the real AMC 8, AMC 10, AMC 12, and AIME problems in our complete solution collection are used with official legal permission of the Mathematical Association of America (MAA).

Concepts:prime factorizationmodular arithmeticbounding to limit cases

Difficulty rating: 3160

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.

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 11Full ExamProblem 13

Problem 12 in Other Years