Greatest common divisor in $\mathbb{F}_p[T]$ with powers of linear polynomials 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). For many $n$ actually $u=0,1$ are sufficient.
I tried to find a proof, but my first idea 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 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. 
 A: 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 $p=3, \ell=11, m=23$ but succeeds for $p=3,\ell=23, m=47$ and $p=3, \ell=29, m=59$.
I found these by looking at the sequence of multiplicative orders of $3$ modulo primes 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);
