IBM Research | Ponder This | September 2003 solutions
Skip to main content

September 2003

<<August September October>>


Solution:

A rational root of Pn(x) is an integer, because n!Pn(x) = n! + n!x + ... + xn is a monic polynomial with integer coefficients (to see this let x = a/b in lowest terms, substitute into n!Pn(x) = 0 and multiply through by bn; then b divides an, a contradiction).

Hence suppose Pn(x) = 0 with x an integer. Now choose a prime p dividing n; then p is odd since n is odd, and since n! + n!x + ... + nxn-1 = 0, it follows that p also divides x.

Next, by definition of Pn,

ex = Pn(x) + Rn(x) and e-x = Pn(-x) + Rn(-x)

where the remainder Rn(x) = xn + 1 / (n + 1)! + ... It follows on multiplying these together that
Pn(x) + Pn(-x) = 1 + xn + 1gn(x)

where gn(x) is a polynomial. Multiplying this through by (n)2 gives
(n!)2Pn(x) + Pn(-x) = (n!)2 + xn + 1Gn(x)

where Gn(x) = (n!)2gn(x) must have integer coefficients because the coefficients on the left hand side are integers. Since Pn(x) = 0, we find that (n!)2 is divisible by xn + 1, hence by pn + 1 where p is the odd prime chosen above.

But by Legendre's formula the greatest power of p that divides n! is
[n / p + n / p2 + ... ≤ n / p + n / p2 + ... = n / (p - 1)

where the [ ] means "greatest integer less than"(strict inequality holds but we do not need this).

Therefore n + 1 ≤ 2n / (p - 1). But then p ≤ 1 + 2n / (n + 1) < 3, a contradiction since p is an odd prime.]


If you have any problems you think we might enjoy, please send them in. All replies should be sent to: webmster@us.ibm.com