document.write( "Question 1182506: Let P(x) be a nonconstant polynomial, where all the coefficients are
\n" ); document.write( "nonnegative integers. Prove that there exist infinitely many positive
\n" ); document.write( "integers n such that P(n) is composite.\r
\n" ); document.write( "\n" ); document.write( "Hint(s):\r
\n" ); document.write( "\n" ); document.write( "Remember that if a and b are distinct integers, then P(a) - P(b) is divisible by a - b. \n" ); document.write( "

Algebra.Com's Answer #812604 by ikleyn(52810) $\"\"$ $\"About$

You can put this solution on YOUR website!
.\r
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "            I saw several proofs to this statement in the Internet (including this forum).\r
\n" ); document.write( "\n" ); document.write( "            Some of them are defective or unsufficient; to others, I don't like them, since they are not convincing.\r
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "            Finally, I found one in the Internet, which is understandable, correct and convincing at the same time.\r
\n" ); document.write( "\n" ); document.write( "            So, I place it here, with the reference. The source is this document \r
\n" ); document.write( "\n" ); document.write( "            https://faculty.math.illinois.edu/~hildebr/putnam/training19/polynomials1sol.pdf\r
\n" ); document.write( "\n" ); document.write( "            of the University of Illinois Math Contest Training Sessions.\r
\n" ); document.write( "
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "

\r\n" );
document.write( "Let  n0 = P(2)  and note that,  since  P(x)  is non-constant  (i.e., has degree at least 1)  and has nonnegative integer\r\n" );
document.write( "coefficients,  n0  is an integer ≥ 2. \r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "Now consider any integer n with n ≡ 2 mod n0. By the general properties of congruences, we have  \r\n" );
document.write( "\r\n" );
document.write( "     ≡  mod n0 for any nonnegative integer i, \r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "and hence \r\n" );
document.write( "\r\n" );
document.write( "     =  +  + . . .  +  ≡\r\n" );
document.write( "\r\n" );
document.write( "         ≡  +  + · · · +  = P(2) mod n0. \r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "Since P(2) = n0,  it follows that  P(n) ≡ 0 mod n0,  so  P(n)  is divisible by  n0  for any such n. \r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "Moreover, since P has nonnegative coefficients and is non-constant, P(x) is increasing in\r\n" );
document.write( "x and so P(n) > P(2) = n0 for any n > 2. \r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "Thus,  n0  is a proper divisor of  P(n)  for any integer  n > 2  with  n ≡ 2 mod n0, \r\n" );
document.write( "\r\n" );
document.write( "and  P(n)  is therefore composite for any such n,  i.e.,  for n = 2 + n0,  2 + 2n0, . . . .\r\n" );
document.write( "

\r
\n" ); document.write( "\n" ); document.write( "The proof is completed.\r
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "By the way, the same proof works for any natural number m > 1 instead of 2, without any change ( ! )\r
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "-------------\r
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "Regarding the \"hint\" at the end of the problem, I think it is IRRELEVANT.\r
\n" ); document.write( "
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "////////////\r
\n" ); document.write( "
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "It is \"instructive\" to read about this UI Math Contest Program from\r
\n" ); document.write( "\n" ); document.write( "https://faculty.math.illinois.edu/~hildebr/putnam/ \r
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "

\r\n" );
document.write( "    The UI Math Contest Program is one of the most extensive and most visible in the country. \r\n" );
document.write( "    It has been considerably expanded in recent years with additional contest opportunities \r\n" );
document.write( "    and an enhanced training program, and participation in our events is at record levels. \r\n" );
document.write( "    Our students have produced outstanding results in national competitions, culminating \r\n" );
document.write( "    in an Honorable Mention for the UI Putnam Team in 2015.\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "    The William Lowell Putnam Competition is an annual math contest for undergraduates \r\n" );
document.write( "    sponsored by the Mathematical Association of America. It has been called the \"world's toughest math test\", \r\n" );
document.write( "    and is widely considered as the most prestigious contest of its kind. More than 4000 students \r\n" );
document.write( "    from colleges and universities in the United States and Canada participate in this contest each year. \r\n" );
document.write( "

\r
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( " \n" ); document.write( "

\n" );