Let $f(x) \in \mathbb{Z}[x]$ and suppose $f(\omega^j) \in \mathbb{Z}$ for all $j= 1, \dots, n$ where $\omega = e^{2 \pi i/n}$ is a primitive $n^{\text{th}}$ root of unity.

Computational evidence suggests

$$ f(\omega^{p^e}) \equiv f(\omega^{p^{e-1}}) (\text{mod } p^e), $$ for all primes $p$ and positive integers $e \geq 1$.

**Is there a proof, or a counterexample?**

Note that by Euler's theorem, for every $a \in \mathbb{Z}$ such that $\text{gcd}(a,n) = 1$ we have $$ a^{\phi(n)} \equiv 1 (\text{mod }n), $$ where $\phi(n) = |\{ k \in [n] : \text{gcd}(n,j) = 1 \}|$ denotes Euler's totient function.

In particular if $n = p^e$, then $\phi(p^e) = p^e-p^{e-1}$ so

$$ a^{p^e-p^{e-1}} \equiv 1 (\text{mod }p^e), $$ whenever $\text{gcd}(a,p) = 1$.

Thus by modular arithmetic we can move the modulo inside the argument and get

$$ f(x^{p^e}) = f(x^{p^e-p^{e-1}} x^{p^{e-1}}) \equiv f(x^{p^{e-1}}) (\text{mod } p^e). $$

Therefore the congruence holds for all integer polynomials at all integer points relatively prime to $p$. My question is if this congruence can be lifted to $n^{\text{th}}$ roots of unity if $f(x)$ takes integer values at all $n^{\text{th}}$ roots of unity?

By the way, if $f(\omega^j) \in \mathbb{Z}$, then it is well-known that $f(\omega^j) \in \mathbb{Z}[\omega + \omega^{-1}]$, so (ignoring the constant term) $f(x)$ has palindromic coefficients.