Interesting numbers $n$ such that $x^n-1=(x^p-x+1)f(x)+pg(x)$ 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.
 A: 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.
A: 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...
