GCD in $\mathbb{F}_3[T]$ with powers of linear polynomials

Question

This is a continuation of my previous question on $\gcd$s of polynomials of type $f^n - f$.

Let us call $n > 1$ simple at a prime $p$ when $p-1 \mid n-1$ but $p^k - 1 \not\mid n-1$ for all $k > 1$.

Let us call $n > 1$ nice at a prime $p$ when $$T^p - T = \gcd((T+u)^n - (T+u) : u \in \mathbb{F}_p).$$

Numerical results suggest that most simple numbers are nice:

• For $p = 2$, there are $5484$ simple numbers $n \leq 10000$, and only $142$ of these (that is $2.6\%$) are not nice, the smallest example being $n = 74$.
• For $p = 3$, I have verified that all simple numbers $n \leq 100000$ (yes, 100 thousand!) are nice.

In the linked MO question, Will Sawin and François Brunault have found a counterexample for $p=3$, which is incredibly large: $$n= 2003046359$$

1. For $p=3$, are there smaller simple numbers that are not nice?
2. For $p=3$, what is the smallest simple number that is not nice? (It has to be $>100000$).

Background. If $n$ is nice, then there is a simple proof that every $n$-ring of characteristic $p$ is a $p$-ring. See also Section 4 in Equational proofs of Jacobson's Theorem.

Answer 1

The smallest counterexample is $n=1+(3^{16}-1)/32$. It seems that SageMath (which uses the flint library as a backend for univariate polynomials over finite fields) is far superior than Gap.

Indeed, the following naive Sage code only needs 16 minutes on my office computer to confirm that there are no counterexamples for $n\le100000$.

Modifying the first two lines and running the code in parallel on 16 cores confirms within a few hours that $n=1+(3^{16}-1)/32=1345211$ is indeed the smallest counterexample.

n = 3 # start value 
step = 2
    
k.<t> = GF(3)[]

def is_simple(n, p):
    if n%(p-1) != 1:
        return False
    P = p^2
    while P <= n:
        if (n-1)%(P-1) == 0:
            return False
        P *= p
    return True

while True:
    print(n)
    if is_simple(n, 3):
        m = n-1
        f = gcd([t^m-1, (t+1)^m-1, (t-1)^m-1])
        if f.degree() > 0:
            print('smallest example: n = ', n)
            break
    n += step

Three bigger yet not too big examples which are not derived from the smallest example are $n=1 + (3^{18}-1)/52$, $n=1 + (3^{20}-1)/220$ and $n=1+(3^{22}-1)/92$. These were obtained by checking factors of $3^k-1$ for $k\le22$. Common divisors of $(t+u)^{n-1}-1$, $u\in\mathbb F_3$, in these cases are $t^{18}+t^{13}-t^{12}+t^{11}+t^9-t^8+t^4+t^3-t+1$, $t^{20}-t^{18}+t^{16}+t^{15}+t^{13}-t^9+t^7+t^5-t^4-t^3+t+1$, and $t^{22} - t^{19} + t^{16} + t^{15} + t^{11} + t^9 + t^8 + t^3 + 1$, respectively.