Can you check this proof? Find all polynomials $P(x)$ with integer coefficients such that for each natural number $n, n$ divides $P(2^n)$

Question

Is this a good proof? I think it is allright but I am not sure. I want to prove this polynomial must be constant, with P(x)=0.

Suppose P isn't constant Let ord_p(2) denote the smallest number 0<k such that 2^k==1 mod p. Let P be of degree k and leading coefficient A. Take p>A and P > 2^k. Then p|P(2^(tp)) for every t, meaning that 2^(tp) is a root of P mod p for every t. As 2^x==2^(x mod ord_p(2)), there is ord_p(2) unique roots of P mod p, all of which can be written as 2^(tp). But as 2^ord_p(2)>p>2^k then ord_p(2)>k, but this is a contradiction as P can have at most k roots mod p (because p does not divide A, as p>A).

Welcome to MSE. For some basic information about writing mathematics at this site see, e.g., basic help on mathjax notation, mathjax tutorial and quick reference, main meta site math tutorial and equation editing how-to. — José Carlos Santos, Jan 01 '24 at 14:52
FYI, using an Approach0 search, there's the AoPS threads Polynomial with integer coefficients and n divides P(2^n), with the latter thread stating the source is "$2016$ ELMO Problem $4$". — John Omielan, Jan 01 '24 at 15:04
Your $a_i$s are complex numbers. Why should $(x-a_1)\dots(x-a_k)$ have integer coefficients? and if it doesn't, "$p|(2^p-a1)(2^p-a2)...(2^p-ak)$" doesn't seem to make sense. — Anne Bauval, Jan 01 '24 at 15:06
So, I think your proof is flawed. Here is a correct and simpler one: To show P is a zero polynomial — Anne Bauval, Jan 01 '24 at 15:15
@AnneBauval Yeah, it was careless to write it up like that, but the proof still works i think, due to the fact that P has at most deg P roots mod p? — TheSega, Jan 01 '24 at 15:34
Which proof? We cannot tell before you rewrite a careful one. — Anne Bauval, Jan 01 '24 at 15:39

Can you check this proof? Find all polynomials $P(x)$ with integer coefficients such that for each natural number $n, n$ divides $P(2^n)$

0 Answers0