stroller wrote: The given condition translates to $p | n- \omega_k \implies p | P(n)^k -1 $ Shouldn't this be $p \mid P(n)^m - 1$ for some $m \leq k$?

fattypiggy123 wrote: stroller wrote: The given condition translates to $p | n- \omega_k \implies p | P(n)^k -1 $ Shouldn't this be $p \mid P(n)^m - 1$ for some $m \leq k$? Sorry my mistake; I misread the problem as $\text{ord}_p(P(n))|\text{ord}_p(n)$

Yes your solution has a few points of contention, for instance $\omega_k$ starts off life as an element of $\mathbb{F}_p$ but somehow becomes an actual complex root of unity halfway through. All of this can be fixed/made rigorous by some algebraic number theory. I will post more on it when I am free.

The main idea to stroller's solution is to attempt to lift the local conditions, $P(u_p) \equiv v_p \pmod p$ where $u_p,v_p$ are integers satisfying $u_p^k , v_p^m \equiv 1 \pmod p$, into a global condition $p \mid P(x) - y$ for some numbers $x,y$ to deduce that $P(x) - y = 0$ since it cannot have infinitely many distinct prime factors. For instance if $k = m = 1$, then we can simply choose $x = y = 1$. The problem comes when $k$ and $m$ are larger than $2$ and one cannot find any integer $x$ such that $x^k \equiv 1 \pmod p$ for infinitely many primes $p$ where $x \not = 1$. As indicated in stroller's solution, we should bring in the complex primitive roots of unity $\omega_k$ and $\omega_m$. For simplicity, I will just assume $m = k$. Now there is a natural place (but not the only one!) to do arithmetic with $\omega_k$. The field $\mathbb{Q}(\omega_k)$ is a number field and so its ring of integers is a Dedekind domain. When working beyond $\mathbb{Z}$, it is known that we cannot hope for unique factorization of integers to continue to hold. What one can achieve however is unique factorization into ideals, which is a property that Dedekind domains possess (and can also be taken as its defining property) and so makes Dedekind domains a nice place to do arithmetic in. In the case of $\mathbb{Q}(\omega_k)$, its ring of integers is simply $\mathbb{Z}[\omega_k]$, which is just sums of $\omega_k^i$ with $\mathbb{Z}$-coefficients. For a prime $p$, let $\mathbb{F}_q$ be the smallest field extension of $\mathbb{F}_p$ where you have a primitive $k^{th}$ root of unity. This always exists if say $p \nmid k$. Then just like how in the usual integers $\mathbb{Z}$, we have the "reduction mod p" maps from $\mathbb{Z}$ to $\mathbb{F}_p$, there will exist reduction maps from $\mathbb{Z}[\omega_k]$ to $\mathbb{F}_q$ for each such $q$ where $\omega_k$ is sent to one of the primitive $k^{th}$ roots of unity in $\mathbb{F}_q$. When $p \nmid k$, the ideal $(p)$ in $\mathbb{Z}[\omega_k]$ factors as a product of distinct prime ideals $\mathfrak{p}_1 \cdots \mathfrak{p}_g$. These reduction maps then arise from reducing modulo $\mathfrak{p}_i$ instead of just mod $p$. For example, if we work over the Gaussain integers $\mathbb{Z}[i]$ instead then we are looking at field extensions $\mathbb{F}_q$ where $x^2 = -1$ has a solution. For $p = 3$, there are no solutions within $\mathbb{F}_3$ itself and so we have to extend to $\mathbb{F}_9$, the field with $9$ elements. Correspondingly, the element/ideal $(3)$ is prime in $\mathbb{Z}[i]$ and so the map $\mathbb{Z}[i] \to \mathbb{F}_9$ arises from $a + bi \mapsto a \pmod 3 + b \pmod 3 i$. You can check that there are then $9$ elements just like $\mathbb{F}_9$. Howeverfor $p = 5$, within $\mathbb{F}_5$ there is already a solution to $x^2 = -1$ and so $\mathbb{F}_q = \mathbb{F}_5$. Our map $\mathbb{Z}[i] \to \mathbb{F}_5$ can't be just reducing mod $5$ then as that will give us $25$ elements instead. Instead one should factor $(5) = (2+i)(2-i)$ and then reduce mod $(2+i)$ or $(2-i)$. Since $x^2 + 1 = 0$ has two solutions in $\mathbb{F}_5$, there are two possible elements one can map $i$ to and each mod corresponds to one of them. As a result, we can lift the local conditions to get for each $p \equiv 1 \pmod k$, there is one prime ideal factor $\mathfrak{p}$ of the ideal $(p)$ that divides $P(\omega_k) - \omega_k^m$ which implies that it must be $0$ by unique factorization of ideals.

Here is alternative way to make stroller's solution rigorous, using elementary method. We will prove that $P(\omega_k)^{k!}=1$. The key idea is to transfer from $\mathbb{Q}(\omega_k)$ to $\mathbb{Z}_p$ properly. However, the difficulty is $\omega_k$ is defined through roots of polynomials, which means we don't know the order of root. We will circumvent this issue by using symmetric polynomials instead. Fix a positive integer $n$ and let $m=\varphi(n)$. Let $\omega_1, \omega_2, ...,\omega_m$ be primitive $n$-th root unity. By Newton's theorem on polynomial on symmetric polynomial, polynomial $$Q(X) = (X-P(\omega_1))(X-P(\omega_2))...(X-P(\omega_m))$$has integer coefficients. Fix a prime $p\equiv 1\pmod n$ and working on $\mathbb{F}_p[X]$. Let $a_1,a_2,...,a_m$ be all residues $\pmod p$ having order $n$. We claim that Claim 1 : Let $$Q^*(X) = (X-P(a_1))(X-P(a_2))...(X-P(a_m))$$then $Q^*(X) - Q(X)$ has all coefficients divisible by $p$. Proof : Let $e_1, e_2,...,e_m$ be Elementary symmetric polynomials of $m$ variables. Then in $\mathbb{F}_p[X]$, $$(X-a_1)(X-a_2)...(X-a_m) = \varPhi_n(X) = (X-\omega_1)(X-\omega_2)...(X-\omega_m)$$Thus comparing coefficients give $e_i(a_1,a_2,...,a_m) \equiv e_i(\omega_1,\omega_2,...,\omega_m) \pmod{p}$ for any $i=1,2,...,m$. (Recall that both numbers are integer!). Therefore, by Newton's theorem on symmetric polynomial, $$e_i(P(a_1),P(a_2),...,P(a_m)) \equiv e_i(P(\omega_1),P(\omega_2),...,P(\omega_m)) \pmod p$$implying the result. Claim 2 : $Q^*(X)$ divides $X^{n!}-1$ (in $\mathbb{F}_p[X]$). Proof : Since $\mathrm{ord}_p(a_1) = n$, we have $\mathrm{ord}_p(P(a_1))\leqslant n$ or $P(a_1)^{n!}\equiv 1\pmod p$. Hence each root of $Q^*(X)$ is root of $X^{n!}-1$, done. Now we are ready to shift the local conditions into global conditions. Since $Q(X)$ must congruent to $Q*(X)$ in $\mathbb{F}_p[X]$, polynomial $Q(X)$ must congruent to some divisor of $X^{n!}-1$ in $\mathbb{F}_p[X]$. By Pigeonhole's principle there exists infinitely many prime $q\equiv 1\pmod n$ which $Q(X)$ is congruent to same divisor $R(X)$ of $X^{n!}-1$ in $\mathbb{F}_q[X]$. This force all coefficients of $Q(X)-R(X)$ to be divisible by infinitely many prime $q$. Hence $Q(X) = R(X)\mid X^{n!}-1$, implying $P(\omega_i)^{n!} = 1$ as desired.

Here's another elementary solution: Fix $n$, and let $p$ vary across all primes equivalent to $1\bmod n$. Now, for all $x$ for which $x^n\equiv 1\bmod p$, we have $$P(x)^{n!}\in\{0,1\}\bmod p\implies P(x)^{n!+1}-P(x).$$ (we get $1$ if we can apply our condition and otherwise we get $0$). Let $Q(x)=P(x)^{n!+1}-P(x)$, and write $$Q(x)=R(x)+S(x)(x^n-1)$$ where $\deg(R)<n$ (we do this in $\mathbb{Z}[x]$). Now, for all $p\equiv 1\bmod n$, we have that $Q(x)\equiv 0\bmod p$ if $x^n=\equiv 1\bmod p$, which means that $R(x)\equiv 0\bmod p$. As $R$ has $n$ roots in $\mathbb{F}_p$ and it is of degree $\leq n-1$, we have that $R$ must be equivalent to the zero polynomial $\bmod p$, and thus all of the coefficients of $R$ are divisible by $p$. Now, as this holds for infinitely many $p$, we see that $R(x)$ is identically $0$, or that $$x^n-1\big|P(x)^{n!+1}-P(x).$$ This implies that, if $x=\zeta_n$ is a primitive $n$th root of unity, $$P(\zeta_n)=0\mathrm{\ or\ }P(\zeta_n)^{n!}=1\implies |P(\zeta_n)|=1.$$ One of these two criteria must hold for infinitely many $n$. If it is the first, then $P$ has infinitely many roots and is identically $0$. If it is the second, then, letting $d$ be the degree of $P$, $$P(z)z^dP\left(\frac{1}{z}\right)=z^d$$ holds for infinitely many $z$; as this is a polynomial equation these must be identical as polynomials. We claim the only solutions to this are of the form $\pm x^d$. Assume we have a counterexample $P$ with minimal degree. As $P(x)/x$ would be a counterexample if $P(0)$ were equal to $0$, we conclude that $P(0)\neq 0$. However, as $z\to\infty$ ($z$ real), the left side is of order $P(0)z^d(cz^d)$ ($c$ is the leading coefficient) while the right side is $z^d$, allowing us to conclude (as $cP(0)\neq 0$), that $d=0$ and $P$ is constant, which implies that if $P\equiv c$ we have $c^2=1$, which is exactly our solution set. Now, if $P(x)=x^d$ we have a valid solution and if $P(x)=-x^d$ we have a contradiction at $n=1$ and $p=3$, so the only solutions are $P(x)=0$ and $P(x)=x^d$, finishing the proof.