# How to show that if $\pi(x) \mid x^{p^n} - x$ then $\deg(\pi(x)) \mid n$?

I'm in the middle of the proof about $$P_n = x^{p^n} - x \in F_p[x]$$ for p prime, being the product of all monic, irreducible polynomials of degree $$d$$ such that $$d \mid n$$.

I've already proved that if $$\pi(x) \in F_p[x]$$ is monic, irreducible, such that $$\deg(\pi(x)) \mid n$$ then $$\pi(x) \mid P_n$$.

I've also proved that there are no irreducible factors with multiplicity in the factorization of $$P_n$$.

It remains to prove that every factor of $$P_n$$ is of the form $$\pi(x)$$, that is, if $$r(x) \in F_p[x]$$ is a monic, irreducible polynomial of degree $$d$$, such that $$r(x) \mid P_n$$, than $$d | n$$.

How can I go on with that to finish the proof? Here's what I was trying:

Let $$\pi(x) \in F_p[x]$$ be a monic and irreducible polynomial of $$\deg(\pi(x)) = d$$, such that $$\pi(x) | P_n$$. Since $$\pi(x) | P_d$$, it implies that $$\pi(x) \mid P_{\gcd(n,d)}$$. Now suppose that $$d \nmid n$$, therefore $$\gcd(n,d) < d$$...

(Now I'm aiming for a contradiction in the fact that $$\pi(x) \mid P_{\gcd(n,d)}$$ or $$\pi(x) \mid P_n$$, but idk how to continue...)

I'm new to finite fields and abstract algebra, so please, if it's possible, don't use more advanced techniques.

Thanks for your time and help.

• Do you know that there exists a finite field of cardinality $p^n$? – Maxime Ramzi Oct 11 '19 at 20:26
• @Max Nope, I'm proving that so I can guarantee the existence of an irreducible polynomial of an arbitrary degree $n$ in $F_p[x]$. With that in hand I can create a field: $F = F_p[x] / \langle r(x) \rangle$ where $r(x)$ is that irreducible of degree n. It'll follow that $|F| = p^n$. – Bruno Reis Oct 11 '19 at 20:57
• Ok, I just thought about it, it's not strictly necessary for the argument I had in mind anyway. Do you know that if $P_d\mid P_n$ then $d\mid n$ ? – Maxime Ramzi Oct 11 '19 at 21:07

Consider the following field : $$F:=\mathbb F_p[x]/(r)$$ (it's a field because $$r$$ is irreducible of course).

This field has $$p^d$$ elements, therefore by Lagrange's theorem applied to $$F^\times$$, we see that each of its elements is a root of $$X^{p^d}-X$$, so $$X^{p^d}-X = \prod_{a\in F}(X-a)$$

Now note the following thing : in a characteristic $$p$$ field, $$(a+b)^{p^k} = a^{p^k}+ b^{p^k}$$ for any integer $$k$$.

It follows that if we let $$\alpha$$ denote the image of $$x$$ in $$F$$, and if $$P$$ is a polynomial, then $$P(\alpha)^{p^n} = P(\alpha^{p^n}) = P(\alpha)$$ (indeed, $$\alpha^{p^n} = \alpha$$ because $$r\mid P_n$$, so $$\alpha$$ is a root of $$p^n$$).

Therefore, $$P(\alpha)$$ is also a root of $$P_n$$. But $$F$$ consists of elements of this form : any element of $$F$$ is a root of $$P_n$$ !

Therefore $$P_d\mid P_n$$, and it's easy to see that this divisibility relation holds in $$\mathbb F_p[x]$$, not only $$F[x]$$ (to see why, think about euclidean division).

Do you know that this implies $$d\mid n$$ ? (I think you do, since you mentioned $$P_{gcd(d,n)}$$) If yes, then we are done. Else, I'll add something to that effect.

• I'll take a look at this later. Ty anyway Max! – Bruno Reis Oct 11 '19 at 21:16
• I agree that if $P_d \mid P_n$ than $d \mid n$ since $\gcd(P_n, P_d) = P_{\gcd(n,d)}$. So if $P_d \mid P_n$, we'll have $\gcd(P_n, P_d) = P_d \implies \gcd(n,d) = d \implies d \mid n$. Correct? – Bruno Reis Oct 11 '19 at 21:20
• Yes, if you know that equality on gcd's then it follows – Maxime Ramzi Oct 11 '19 at 21:22