Interesting numbers $n$ such that $x^n-1=(x^p-x+1)f(x)+pg(x)$

Question

I'm dealing with the test of the International Mathematics Competition for University Students, 2011, and I've had a lot of difficulties, so I hope someone could help me to discuss the questions.

I've posted before the questions 2 and 5, and this last is still open.

Well, the question 3 says that:

Let be $p$ a prime number. We say that a positive integer $n$ is interesting if

$x^n-1=(x^p-x+1)f(x)+pg(x)$

where $f$ and $g$ are polynomials with integer coeficients.

(a) Prove that the number $p^p-1$ is interesting.

(b) For which $p$ the number $p^p-1$ is the minimal interesting number?

Well, I unfortunately couldn't do a lot on item a), and I couldn't even understand the item b).

The item a) ask a proof: "the number $p^p-1$ is interesting". So, in any case, this number is interesting... I couldn't understand the item b).

Particularly, I've tried prove that $p^p-1$ is interesting when $p=2$ (earliest prime) and got the following:

$p=2\Longrightarrow p^p-1=3$

Let be $f(x)=x+1$ and $g(x)=-1$, so

$x^{p^p-1}-1=(x^p-x+1)f(x)+pg(x)$.

In fact,

$x^3-1=(x^2-x+1)(x+1)-2$.

Thanks very much.

Answer 1

I'll do part $(a)$.

Let $p$ be a prime, and let $n=p^p-1$.

The goal is to show that there exist $f,g\in\mathbb{Z}[x]$ such that $$x^n-1=(x^p-x+1)f(x)+pg(x)$$ or equivalently, that in $Z_p[x]$, we have $$(x^p-x+1){\,\mid\,}(x^n-1)$$

Note that in $Z_p[x]$, we have $(a+b)^p=a^p+b^p$.

Let $h\in Z_p[x]$ be given by $h=x^p-x+1$.

Then in $Z_p[x]$, working mod $h$, we have \begin{align*} x^p&\equiv x-1\;(\text{mod}\;h)\\[8pt] \implies\;x^{p^2}&\equiv (x-1)^p\;(\text{mod}\;h)\\[4pt] &\equiv x^p-1\;(\text{mod}\;h)\\[4pt] &\equiv (x-1)-1\;(\text{mod}\;h)\\[4pt] &\equiv x-2\;(\text{mod}\;h)\\[8pt] \implies\;x^{p^3}&\equiv (x^p-1)^p\;(\text{mod}\;h)\\[4pt] &\equiv x^{p^2}-1\;(\text{mod}\;h)\\[4pt] &\equiv (x-2)-1\;(\text{mod}\;h)\\[4pt] &\equiv x-3\;(\text{mod}\;h)\\[8pt] &\;\;\vdots\\[8pt] \implies\;x^{p^p}&\equiv x-p\;(\text{mod}\;h)\\[4pt] &\equiv x\;(\text{mod}\;h)\\[8pt] \implies\;x^{p^p-1}&\equiv 1\;(\text{mod}\;h)\\[4pt] \end{align*} It follows that in $Z_p[x]$, we have $$(x^p-x+1){\,\mid\,}(x^n-1)$$ as was to be shown.

Answer 2

The key word is Artin-Schreier theory.

Let $K=\Bbb F_p$ be in the notation of loc. cit. the prime field with $p$ elements. The we have $k^p=k$ for all $k\in K$. So the polynomial $A=x^p-x+1$ has no roots in $K$.

So $A$ is irreducible over $K$.

Let $a$ be a root of $A$ in some field extension. The roots of $A$ are then of the shape $a+k$ for $k\in K$, i.e. $k$ is $0,1,\dots,(p-1)$, because they are different, are roots, $$ \begin{aligned} A(a+k) &=(a+k)^p-(a+k)+1\\ &=(a^p+k^p)-(a+k)+1\\ &= (a^p-a+1)+(k^p-k)\\ &=A(a)+0=0\ , \end{aligned} $$ and there are $p=\deg A$ of them.

The $p$-Frobenius morphism maps $a$ to $a^p=a-1$.

Applying it once more we have $a^{p^2}=(a-1)^p=a^p-1^p=(a-1)-1=a-2$, and so on.

We denote by $F$ the splitting field $F=K(a)$. It has $p^p$ elements. Because $a$ is a non-zero element in the multiplicative group $F^\times$ with $n=p^p-1$ elements, we have $$ a^n=1\ . $$ This holds for all (distinct) roots of $A$, so $A=\prod_{k\in K}(X-(a+k))$ divides $X^n-1$. This shows the first point.

For the second point, the question is when $a$ (or equivalently one of its conjugates) is a multiplicative generator of the cyclic group $F^\times$.

Time for an experiment, using sage:

sage: for p in primes(20):
....:     R.<x> = PolynomialRing( GF(p) )
....:     F.<a> = GF( p^p, modulus = x^p - x + 1 )
....:     r = ZZ( (p^p-1) / a.multiplicative_order() )
....:     print "p = %2s :: (%2s^%-2s-1) / |a| = %s" % ( p, p, p, r )
....:     # print "... roots of x^%s - a are %s" % ( r, (x^r-a).roots(ring=F, multiplicities=0) )
....: 
p =  2 :: ( 2^2 -1) / |a| = 1
p =  3 :: ( 3^3 -1) / |a| = 1
p =  5 :: ( 5^5 -1) / |a| = 2
p =  7 :: ( 7^7 -1) / |a| = 3
p = 11 :: (11^11-1) / |a| = 5
p = 13 :: (13^13-1) / |a| = 6
p = 17 :: (17^17-1) / |a| = 8
p = 19 :: (19^19-1) / |a| = 9
sage: 

The pattern is now clear. Let $p\ge 5$ be a prime number, we write it as $$p=2r+1\ ,$$ and we will show that for a root $a$ of $A$ in the field $F$ with $p^p$ elements we have $$ a^{(p^p-1)/r}=1\ . $$ This will follow from $$ a^{1+p+p^2+\dots+p^{p-1}}=-1\ . $$ After splitting the above as a product of powers of Frobenius applied on $a$, we have to show: $$ a(a-1)(a-2)\dots(a-p-1) = -1\ , $$ which is the formula computing the norm of $a$ on the L.H.S, and the value of the norm extracted by Vieta from the knowledge of the minimal polynomial $x^p-x+1$ of $a$.

The cases $p=2$, $p=3$ have to be considered explicitly, the code above confirms these are the only primes satisfying the requirements in the second point.

Note: The code was inserted to see if the multiplicative order of $a$ drops further. This was not the case...