Zhero wrote: so $p^k$ fully divides $\gcd(P(p) - P(0), P(p+1) - P(1), P(p+2) - P(2), \ldots)$. Why did you prove this?

I think a better question to ask is "what was I thinking when I wrote up my proof?" I appear to have made a number of typos from a previous (even more incorrect) solution that I'd managed to confuse with my actual proof. Hopefully there are no mistakes in this corrected version:

Zhero wrote: I think a better question to ask is "what was I thinking when I wrote up my proof?" I appear to have made a number of typos from a previous (even more incorrect) solution that I'd managed to confuse with my actual proof. In fact, I didn't see where your former proof is wrong. :

I kept alternating between $\gcd(P(p) - P(0), P(p+1) - P(1), \ldots)$ and $\gcd(P(p^k) - P(0), P(p^k+1) - P(1), \ldots)$ in my first post. In my first attempt at a solution, I claimed that any $n = p$ not dividing $Q(0)(2^k - 1)$ suffices by showing that $p^2 \not | P(2p) - P(p)$, which is completely false for $k \geq 2$. I then claimed that any $n = p^k$ suffices, but forgot to change some of the $P(p) - P(0), P(p+1) - P(1), \ldots$'s to $P(p^k) - P(0), P(p^k+1) - P(1), \ldots$. In particular, I thought that showing $p^k$ fully divides $P(2p) - P(p)$ would be sufficient, when it is actually irrelevant (it was relevant when I thought I was dealing with $\gcd(P(p) - P(0), P(p+1) - P(1), \ldots)$.) The analogous claim would have been that $p^k$ fully divides $P(p^k + p) - P(p)$, which again appears to be false for $k \geq 2$. I fixed this claim in my second post by considering $P(p^k + 1) - P(1)$ instead.

I think we don't need to use that polynomial Q which was used by Zhero, and that we can make the proof much more readable. I think in particular that we can prove that $p^{k+1}$ doesn't divide $P(p^k + 1) - P(1)$ with less work.

Just out of curiosity, how would you do so? As was mentioned in my second post (the first one's wrong), $p^{k+1} \not | P(p^k + 1) - P(1)$ if and only if $p \not \, | \, k Q(1) + Q'(1)$. Perhaps I am missing something obvious, but I don't see how we can show $p \not | k Q(1) + Q'(1)$ without defining $Q$ in the way I did. Nonetheless, I welcome any approach that could make it cleaner. Could you please show your solution?

After showing that $p|\gcd(P(n)-P(0),\ldots)\implies p|n$, note that \[\frac{P(n+k)-P(k)}{n}\equiv P'(k)\pmod{n},\]so because $P'(x)$ cannot infinitely often be zero ($P$ is clearly not constant), we can assume $P'(k)\ne0$ and take infinitely many $n$ with $\gcd(n,P'(k))=1$.

Excuse me Zhero. Just ignore my previous message.

Suppose $P(x)=\sum a_ix^i$ and $deg(P(x))=d$. Now suppose there exist finitely many such $n$. Thus we get $gcd=nt_n$ for all $n>N$ where $N$ be a finite natural number. Now it’s not difficult to see $t_n$ is not bounded. Now obviously we can $P(x+n)-P(x)=n(g(x)+n^2h(x,n))$ where $h(x,n$ be a poly in $x,n$ and $g(x)$ be in $x$. Consider a $n>N$ .Now certainly there exist some $x$ for which $t_n|h(x,n)$. So for those $x$ we get $t_n|g(x)$. Now consider $n=p^k$ where $k$ is a large number and $p>d$. Now suppose a prime $q$ other than $p$ divides $t_n$ and $q$ be the largest among the prime divisors of $t_n$ , suppose $q>p$ .Now consider two sets, $A=\{P(0),P(1),.....P(q-1)\},B=\{P(0),P(1),....,P(q-1)\}$. Note any $i$ th element from $A$ maps to some $j$ th element other than $i$ of $B$ or same happens from $B$. But also this mapping from one set to another is one to one. Basically here mapping means, suppose $q|a-b$ then it’s called $a$ is mapped to $b$ or say $b$ is mapped to $a$. Now basically we’ve $P(0)\equiv\ P(1)\equiv\ P(2)....\equiv P(q-1) (mod q)$ so then we get $q|P(x)$ for all $x$ ,but then we must have $q|gcd(P(0),P(1),P(2),...)$ , and that’s absurd. So $t_n$ must be some power of $p$. Now so ultimately we get $p|g(x)$ for all $x$. But now it’s well known that if some polynomial $f(x)$ is divisible by a prime $p$ less that it’s degree then we must have all of the coefficients of $f(x)$ are divisible by $p$. Now just by induction it’s easy to show all coefficients of $g(x)$ are of type $ia_i$ for all $1\leq i\leq d$. As now we have $p|ia_i$ for all $i$, directly that implies $p|a_i$ for all $ 1\leq i\leq d$ since $p>d$. But again that’s contradicts the fact $ gcd(P(0),P(1),P(2),....)=1$, and thus finally we’re done to show existence of infinitely many such $n$.

First I will show that if $q|P(p+t)-P(t)$ for all $t$ where $q$ and $p$ are some primes,then $q=p$. Let us suppose the contrary.Now clearly by the hypothesis,there is a $t$ such that $q \nmid P(t)$. Take a $k$ such that $q|kp+t$.Then $q|P(kp+t)$ as $P(0)=0$. Now we will prove that $q \nmid P(kp+t)$ for any integer $k$.$q|P(p+t)-P(t)$.Hence $q \nmid P(p+t)$. Let $q \nmid P(kp+t)$.But $q|P(p+{kp+t})-P(kp+t)$.Hence $ q \nmid P((k+1)p+t)$ and hence we are done by induction.So contradiction and hence $q=p$. Now we will prove that infinitely many primes are there such that $gcd(P(p+i)-P(i))=p$.For that we prove that we can find prime $p$ such that $p \nmid \frac{P(p+t)-P(t)}{p}$Calculation yields $\frac{P(p+t)-P(t)}{p} \equiv P^{'}(t) (mod p)$.Hence we take primes $p > |P{'}(t)|$. Please point out any mistake. P.S:And yes we will obviously get a $t$ such that $P^{'}(t) \neq 0$ because otherwise $P(x)$ would be the 0 polynomial contradicting the second hypothesis.

IF kQ(1)+Q'(1)=0? Zhero

The central idea is to ask, "when can a polynomial be zero $\pmod{p}$ where $p$ is prime?" It is well known that the answer is when $p$ divides all its coefficients (necessary and sufficient), or when $p$ is strictly smaller than the degree (necessary, but insufficient). Let $Q(x):=P(x+n)-P(x)$. Write $P(x)=\sum_{k=0}^{\delta} a_{k}x^k,\ a_{\delta} \neq 0$. Taking $Q(x)=\sum_{k=1}^{\delta-1} b_k x^k$, who has $b_{\delta-1}=a_{\delta}\tbinom{\delta}{1}n$ and $b_0=P(n)-P(0)$, it suffices to find infinitely many $n$ with $\gcd(b_0,b_1,\dots,b_{\delta-1})=n$ and $n\in N$ where $N$ is the set of integers whose prime divisors are all $\geq \delta-1$. Factorize $a_{\delta}\tbinom{\delta}{1}=\prod c_i^{e_i}$, and note that by Dirichlet, $N\pmod {c_i}$ is a reduced residue class. By hypothesis there are then infinitely many $n\in N$ so that $\gcd(P(n)-P(0),c_i^{e_i})=1$, since else $\forall x,\ P(x)\equiv P(0)\equiv 0\pmod{c_i}$. The Chinese Remander Theorem finishes the problem $\Box$

USA TST 2010/2 wrote: Let $P$ be a polynomial with integer coefficients such that $P(0)=0$ and \[\gcd(P(0), P(1), P(2), \ldots ) = 1.\]Show there are infinitely many $n$ such that \[\gcd(P(n)- P(0), P(n+1)-P(1), P(n+2)-P(2), \ldots) = n.\] All prime numbers $n=p>|P'(a)|>0$ satisfy the condition, where $a$ is some positive integer. First, $n \mid P(n+k)-P(k)$ for all $k \geqslant 1$ so $n$ is a factor of that gcd, say, $g_n$. If $q \mid g_n$ is a prime and $q \nmid n$ then we have $$P(jn) \equiv P((j-1)n) \equiv \dots \equiv P(0)=0 \pmod{q}.$$However, $\{jn\}_{j \ge 1}$ spans all residues mod $q$ so $q$ divides all values $P$ takes over inputs from $\mathbb{N}$, contradiction! Also, if $p^2 \mid g_n$ then we have, by Taylor's expansion, $$0 \equiv P(n+a)-P(a) \equiv nP'(a) \pmod{p^2},$$which fails due to size conditions on $n$. Hence, infinitely many $n$ satisfy this condition. $\blacksquare$

Nothing new from the above solutions, but posting for storage. Let $p$ be a prime divisor of $\gcd(P(n)- P(0), P(n+1)-P(1), P(n+2)-P(2), \ldots)$. We claim that $p \mid n$. Indeed, suppose not. We have \begin{align*} P(k + n) \equiv P(k) \pmod{p} \end{align*}for all $k \in \mathbb{Z}_{\geq 0}$. Applying this repeatedly (recall that $P(0) = 0$), we find that \begin{align*} P(kn) \equiv P(0) \equiv 0 \pmod{p}. \end{align*}Since $n \not\equiv 0 \pmod{p}$, as $k$ ranges across the nonnegative integers, $kn$ achieves all modulo $p$ residues. Therefore, we in fact have \begin{align*} P(k) \equiv 0 \pmod{p} \end{align*}for all $k$, contradicting the fact that $\gcd(P(0), P(1), \ldots) = 1$. Therefore, $p \mid n$, as claimed. Additionally, note that $P(n + k) \equiv P(k) \pmod{n}$ for all $k \in \mathbb{Z}_{\geq 0}$, so $n \mid \gcd(P(n)- P(0), P(n+1)-P(1), P(n+2)-P(2), \ldots)$. This is enough to imply that when $p$ is prime, $\gcd(P(p)- P(0), P(p+1)-P(1), P(p+2)-P(2), \ldots)$ is a power of $p$. We will show that for all large enough primes, it is in fact equal to $p$. Let $P(x) = a_dx^d + a_{d - 1}x^{d - 1} + \cdots + a_1x$ (recall that $P(0) = 0$). Expanding with the Binomial Theorem, we find that \begin{align*} \frac{P(x + p) - P(x)}{p} \equiv da_dx^{d - 1} + (d - 1)a_{d - 1}x^{d - 2} + \cdots + a_1 \pmod{p}. \end{align*}Note that the right side is a polynomial in $x$. For $p$ extremely large, by Lagrange's theorem the right side has at most $d - 1$ roots modulo $p$. Therefore, there exists $x$ such that the right side is nonzero modulo $p$. For this choice of $x$, we have $\nu_p\left(P(x + p) - P(x)\right) = 1$, implying that $\gcd(P(p)- P(0), P(p+1)-P(1), P(p+2)-P(2), \ldots) \mid p$. Recalling that $n \mid \gcd(P(n)- P(0), P(n+1)-P(1), P(n+2)-P(2), \ldots)$ for all $n$, we find that $\gcd(P(p)- P(0), P(p+1)-P(1), P(p+2)-P(2), \ldots) = p$. Thus, all large enough primes satisfy the given, which is enough to conclude. $\Box$

In fact, we can find infinitely many primes that work. This is the main idea and simplifies the analysis from a general $n$. Define $\Psi(n) = \gcd(P(n)-P(0),P(n+1)-P(1),\ldots)$. First, note that for any $n$, we have $n\mid P(n+k)-P(k)$ for all $k\ge 0$. So $n\mid \Psi(n)$. Lemma: If a prime $q\mid \Psi(n)$, then $q\mid n$. Proof: Since $P(0)=0$, we have $P(n)\equiv 0\pmod{q}$. Then $P(2n)\equiv 0 \pmod{q}$ as well, and so on, so $P(an) \equiv 0 \pmod{q}$ for all $a\ge 0$. If $q\nmid n$, then $\{0,n,2n,\ldots\}$ covers all residues $\pmod{q}$, so $P(x) \equiv 0 \pmod{q}$ for all $x$. This contradicts $\gcd(P(0),P(1),\ldots)=1$. $\blacksquare$ The Lemma proves that $\Psi(p)$ is some power of $p$. We claim sufficiently large primes $p$ satisfy $\Psi(p)=p$. Suppose instead that $p^2 \mid \Psi(p)$ for sufficiently large $p$. Then \[ p \mid \frac{P(p+k)-P(k)}{p} \quad \forall k\ge 0. \]Define $Q(x) = \tfrac{P(x+p)-P(x)}{p}$. Let $\deg P(x)=d$, then $\deg Q(x)=d-1$. We know from above that $Q(x) \equiv 0 \pmod{p}$ for all $x$. By Lagrange's Theorem (essentially Fundamental Theorem of Algebra for $\mathbb{F}_p$), one of the following two are true: Each coefficient of $Q(x)$ is $0\pmod{p}$. We will show this is impossible; in particular, consider the coefficient of $x^{d-1}$. If $P(x)=a_dx^d+a_{d-1}x^{d-1}+\cdots+a_0$, then \[ Q(x) = \frac{P(x+p)-P(x)}{p} = a_d\binom{d}{1}x^{d-1} + \cdots .\]But only finitely many primes divide the fixed value $a_d\tbinom{d}{1}$, so for sufficiently large $p$, $Q(x)$ does not have all coefficients $0\pmod{p}$. There are at most $d-1$ values for which $Q(x) \equiv 0 \pmod{p}$. Since the first bullet is impossible, the second bullet must be true. But now if $p>d-1$, we have a contradiction.

Let $N$ be some arbitrarily large positive integer. We claim that there exists some value of $N$ such that the infinitely many primes $p$ strictly larger than $N$ satisfy the above property that $d=p,$ where $$d=\gcd((P(p)-P(0),P(p+1)-P(1),P(p+2)-P(2),\cdots).$$Using the well-known fact that $a-b\mid P(a)-P(b)$, it is easy to see that $p=(p+i)-i\mid P(p+i)-P(i)$ for all nonnegative integers $i$, so it follows that $p\mid d$, implying that $\nu_p(d)\ge1.$ Now consider whether $p^2\mid P(p+i)-P(i)$ for all such $i$. Setting $\deg(P)=m$ and $$P(X)=c_mX^m+c_{m-1}X^{m-1}+\cdots+c_1X$$as $P(0)=0$, we find by the Binomial Theorem that \begin{align*} P(p+i)-P(i)&=\sum_{j=1}^mc_j((p+i)^j-i^j)\\ &\equiv\sum_{j=1}^mc_j\left(p^j+\binom{j}1p^{j-1}i+\cdots+\binom{j}{j-2}p^2i^{j-2}+\binom{j}{j-1}pi^{j-1}+i^j-i^j\right)\pmod{p^2}\\ &\equiv p\sum_{j=1}^mc_jji^{j-1}\pmod{p^2}. \end{align*}Defining the polynomial $g(X)=\sum_{j=1}^mc_jjX^{j-1}$, we observe that we simply take $N>g(i)$ for any $i$, as such a setup would imply that $g(i)<p$, forcing $P(p+i)-P(i)$ to not be divisible by $p^2.$ It follows by such a setup that $\nu_p(d)=1.$ Now let $q\neq p$ be another prime, and suppose that $q\mid d,$ implying that $P(p+i)\equiv P(i)\pmod{q}.$ For any positive integer $k$, we see that $P(kp)\equiv P((k-1)p)\equiv\cdots\equiv P(p)\equiv P(0)\pmod{q},$ and since $P(0)=0$ we therefore deduce that $q\mid P(kp)$ for all such $k$. But this implies that the equation $P(X)\equiv0\pmod{q}$ has infinitely many roots, all of the form $kp\not\equiv0\pmod{q}$, so by Lagrange's Theorem we deduce that $P(X)$ modulo $q$ is exactly the zero polynomial. Hence $q\mid\gcd(P(0),P(1),\cdots),$ contradicting the fact that $\gcd(P(0),P(1),\cdots,)=1$ as given. Thus $q\nmid d$ for all other primes. It therefore follows that $p$ is the only prime dividing $d$, with $\nu_p(d)=1$, so we conclude that $p=d$ for infinitely many $p>N$, as desired. $\blacksquare$ - Jörg

Set $n$ to a sufficiently large prime $p$, and let $d$ be the $\gcd$ of interest. Note that for any prime $q\neq p$, we cannot have $$0\equiv P(0)\equiv P(p)\equiv P(2p)\equiv \cdots\equiv P((q-1)p)\pmod{q}$$ so $q\nmid d$. Now, note that the polynomial $P(x+p)-P(x)$ mod $p^2$ is of the form $pQ(x)$, where the coefficients of $Q$ do not depend on $p$. Hence if we take $p >> $ the degree and the sum of the absolute values of the coefficeints of $Q$, we can find $x$ for which $p\nmid Q(x)$ and hence $p^2\nmid P(x+p)-P(x)$, so $p^2\nmid d$ as desired.

I claim that all primes $p$ that are sufficiently large work. First if $q \neq p$ and $q|P(k+n)-P(k)$ then $q|P(n), \forall n$ contradicting the first statement. We have $P(k+n)-P(k)=n^2Q(k,n)+nt$ for some finite integer $t$. Now setting $n=p$ we see that all primes $p>|t|$ satisfy.

Here we go: Consider a prime $p=n$ such that: $p > |P'(a)|$ for some positive integer $a$. Let $g_n = \gcd(P(n)- P(0), P(n+1)-P(1), P(n+2)-P(2), \ldots)$. Evidently, $p|g_n$. Now, say a prime $q$ other than $p$ divides $g_n$. Then: $q|P(n) = P(p)$. Thus: $q|P(pk)$ for all $k = 1, 2, \cdots, q$. Notice that for $k = 1, 2, \cdots, q$, the expression $pk$ ranges all over the residues modulo $q$. Therefore: $P(k) \equiv 0 \pmod p$ for all non-ngative integers $n$. But this contradicts that: $\gcd(P(0), P(1), P(2), \ldots ) = 1.$ Contradiction. Assume that $p^2 | g_n$. Then, due to Taylor Expansion (centred at $x=a$): $$P(p+a)-P(a) \equiv 0 \pmod {p^2} \implies 0 \equiv P(p+a)-P(a) \equiv p P'(a) \pmod {p^2}$$But: $p > |P'(a)|$ which leads to contradiction.