Question 1182506
.


            I saw several proofs to this statement in the  Internet  (including this forum).

            Some of them are defective or unsufficient;  to others,  I don't like them,  since they are not convincing.


            Finally,  I found one in the  Internet,  which is understandable,  correct and convincing at the same time.

            So,  I place it here,  with the reference.   The source is this document  

            https://faculty.math.illinois.edu/~hildebr/putnam/training19/polynomials1sol.pdf

            of the  University of  Illinois  Math  Contest  Training  Sessions.



<pre>
Let  n0 = P(2)  and note that,  since  P(x)  is non-constant  (i.e., has degree at least 1)  and has nonnegative integer
coefficients,  n0  is an integer ≥ 2. 


Now consider any integer n with n ≡ 2 mod n0. By the general properties of congruences, we have  

    {{{n^i}}} ≡ {{{2^i}}} mod n0 for any nonnegative integer i, 


and hence 

    {{{P(n)}}} = {{{a[1]*n^(k-1)}}} + {{{a[2]*n^(k-2)}}} + . . .  + {{{a[k]*n^0}}} ≡

         ≡ {{{a[1]*2^(k-1)}}} + {{{a[2]*2^(k-2)}}} + · · · + {{{a[k]*2^0}}} = P(2) mod n0. 


Since P(2) = n0,  it follows that  P(n) ≡ 0 mod n0,  so  P(n)  is divisible by  n0  for any such n. 


Moreover, since P has nonnegative coefficients and is non-constant, P(x) is increasing in
x and so P(n) > P(2) = n0 for any n > 2. 


Thus,  n0  is a proper divisor of  P(n)  for any integer  n > 2  with  n ≡ 2 mod n0, 

and  P(n)  is therefore composite for any such n,  i.e.,  for n = 2 + n0,  2 + 2n0, . . . .
</pre>

The proof is completed.


By the way, &nbsp;the same proof works for any natural number m > 1 &nbsp;instead of &nbsp;2, &nbsp;without any change &nbsp;(&nbsp;!&nbsp;)


-------------


Regarding the &nbsp;"hint" &nbsp;at the end of the problem, &nbsp;I think it is &nbsp;IRRELEVANT.



////////////



It is &nbsp;"instructive" &nbsp;to read about this &nbsp;UI &nbsp;Math &nbsp;Contest &nbsp;Program from

https://faculty.math.illinois.edu/~hildebr/putnam/ 


<pre>
    The UI Math Contest Program is one of the most extensive and most visible in the country. 
    It has been considerably expanded in recent years with additional contest opportunities 
    and an enhanced training program, and participation in our events is at record levels. 
    Our students have produced outstanding results in national competitions, culminating 
    in an Honorable Mention for the UI Putnam Team in 2015.


    The William Lowell Putnam Competition is an annual math contest for undergraduates 
    sponsored by the Mathematical Association of America. It has been called the "world's toughest math test", 
    and is widely considered as the most prestigious contest of its kind. More than 4000 students 
    from colleges and universities in the United States and Canada participate in this contest each year. 
</pre>