Let $n>1$ and $p$ be an odd prime with $p-1 \mid n-1$ such that $p^k - 1 \mid n-1$ does not hold for any $k>1$. Notice that, since $p-1 \mid n-1$, we have $T^p - T \mid T^n-T$ in $\mathbb{F}\_p[T]$ and hence also $T^p - T = (T+u)^p - (T+u) \mid (T+u)^n - (T+u)$ for all $u \in \mathbb{F}\_p$.


**Question.** Is $T^p - T$ actually the gcd of $\{(T+u)^n - (T+u) : u \in \mathbb{F}\_p\}$ in $\mathbb{F}\_p[T]$?


I have verified this with computer algebra software for $n \leq 7000$ ([code link](https://pastebin.com/mDCuwkdP)). For many $n$ actually $u=0,1$ are sufficient.


I tried to find a proof, but [my first idea](https://math.stackexchange.com/questions/3549841) didn't work. The only thing I know so far is that the gcd is invariant under $T \mapsto T+1$ and therefore contained in $\mathbb{F}\_p[T^p-T]$. I expect that there are two proofs (if the statement is true at all), namely one using finite fields $\mathbb{F}\_{p^m}$, and one using a direct calculation with polynomials. I am more interested in a direct calculation here. The background is a new proof of [Jacobson's theorem](https://ysharifi.wordpress.com/tag/jacobson-theorem/) I am working on. Notice that the statement is false for $p=2$ (but still true for many $n$ in this case) and that it is clearly false without the $p^k-1$-requirement. 



Greatest common divisor in $\mathbb{F}_p[T]$ with powers of linear polynomials
This is false.


Let $p$ be an odd prime, let $\ell$ be another prime, and let $m$ be a small prime divisor of $p^{\ell}-1$, that doesn't divide $p-1$. Let $n= 1 + \frac{ p^{\ell}-1}{m}$. 


Then $n-1$ is a multiple of $p-1$, is not a multiple of $p^{\ell}-1$, and is not a multiple of $p^{k}-1$ for any other $k$ because $p^{\ell}-1$ is not a multiple of $p^{k}-1$ for any $1 < k < \ell$. 


Then $x \in \mathbb F\_{p^\ell}$ is a root of $T^{n } - T$ if and only if $x$ is an $m$'th power in $\mathbb F\_{p^\ell}$. So roots of the gcd of $(T+u)^n - (T+u)$ for all $u$ in $\mathbb F\_p$ are exactly those $x \in \mathbb F\_{p^\ell}$ such that $x = y\_0^m, x+1 = y\_1^m, \dots, x+p-1 = y\_1^{m}$ for some $y\_0, \dots, y\_{p-1}$ in $\mathbb F\_{p^\ell}$. 


Thus, to find a counterexample, it suffices to check that the number of $\mathbb F\_{p^\ell}$ points of the curve $C\_m$ with variables $x,y\_0,\dots, y\_{p-1}$ and equations $x +i = y\_i^m$ is greater than the number $p m^{p-1}$ of solutions with $x \in \mathbb F\_p$. Then the $x$ coordinates of the extra points will be roots of the gcd but not roots of $T^p- T$.


By Riemann-Hurwitz, the genus $g$ of $C$ satisfies $$2-2g = 2 m^p - (p+1) m^{p-1} (m-1)$$ since the degree over $\mathbb P^1$ (under the map $x$) is $m^p$, there are $p+1$ branch points $0,1\dots, \infty$, and each branch point has ramification of order $m$ on each point lying above it. There are $m^{p-1}$ missing points at $\infty$.


So by Weil's theorem, the number of $\mathbb F\_{p^\ell}$-points of $C$ is at least $$p^\ell - p^{\ell/2} ((p+1) m^{p-1} (m-1) + 2 - 2 m^p) +1 - m^{p-1}$$
with the first term the main term, the second term coming from the Frobenius eigenvalues, and the last term coming from the missing points.


Thus, as long as


$$ p^\ell > p^{\ell/2} ((p+1) m^{p-1} (m-1) + 2 - 2 m^p) + m^{p-1} + p m^{p-1},$$ there is a counterexample.


Plugging into Wolfram Alpha, this inequality fails [for](https://www.wolframalpha.com/input/?i=3%5E%7B11%7D%20%20-%20%28%203%5E%7B%20%2811%29%2F2%7D%20%20*%20%284%20*%2023%5E2%20*22%20%20%2B%202%20-%202%20*%2023%5E3%20%29%20%2B%2023%5E2%20%2B%203%20*%2023%5E2%29) $p=3, \ell=11, m=23$ but succeeds [for](https://www.wolframalpha.com/input/?i=3%5E%7B23%7D%20%20-%20%28%203%5E%7B%20%2823%29%2F2%7D%20%20*%20%284%20*%2047%5E2%20*46%20%20%2B%202%20-%202%20*%2047%5E3%20%29%20%2B%2047%5E2%20%2B%203%20*%2047%5E2%29) $p=3,\ell=23, m=47$ [and](https://www.wolframalpha.com/input/?i=3%5E%7B29%7D%20%20-%20%28%203%5E%7B%20%2829%29%2F2%7D%20%20*%20%284%20*%2059%5E2%20*58%20%20%2B%202%20-%202%20*%2059%5E3%20%29%20%2B%2059%5E2%20%2B%203%20*%2059%5E2%29) $p=3, \ell=29, m=59$.


I found these by looking at [the sequence of multiplicative orders of $3$ modulo primes](https://oeis.org/A062117) and looking for prime values, which became $\ell$, with the modulus prime becoming $m$.


It seems there are many examples with $\ell$ not much smaller than $m$, which as long as both are much larger than $p$, means this inequality is easily satisfied, since anything of the form $p^\ell$ beats anything of the form $m^p$. 




---


In the comments, François Brunault found an explicit example: The polynomial $$T^{23}-T^{22}-T^{21}-T^{20}-T^{19}+T^{18}-T^{16}+T^{13}+T^{12}+T^{11}-T^{10}+T^8+T^6+T^4-T^2-T-1$$ divides $$\gcd( T^{n} - T, (T-1)^n - (T-1) , (T+1)^n - (T+1))$$ in $\mathbb F\_3[T]$ when $n= 1 + \frac{3^{23}-1}{47}$ and provided the following Pari/GP code to check it:


`P = Mod(x^23-x^22-x^21-x^20-x^19+x^18-x^16+x^13+x^12+x^11-x^10+x^8+x^6+x^4-x^2-x-1, 3); n = 1 + (3^23-1)/47; t = Mod(x, P); print(t^n == t & (t+1)^n == t+1 & (t-1)^n == t-1);`


