Easy irreducibility over $\mathbb{F}_5$ One of the last days I was looking for help in a problem here and, somewhere, I saw someone asking something that involved the irreducibility of the polynomial $f(x)=x^4+2$ over $\mathbb{F}_5$. In that case the argment was that since $f$ has no roots in $\mathbb{F}_5$ it is enough to check if $gcd(x^4+2,x^{24}-1)=1$. This gcd was calculated as follows:$$gcd(x^4+2,x^{24}-1)=gcd(x^4+2,(-2)^6-1)=1$$ I understood that computation and then I kept my life happilly.
However, when I was solving another problem, I needed to verify the reducibility or irreducibility of the polynomial $f(x)=x^4+1$ over $\mathbb{F}_5$. I know that this polynomial is reducible since $x^4+1=x^4-4=(x^2+3)(x^2+2)$ but I would like to see that in that case the $gcd(x^4+1,x^{24}-1)$ would be different of $1$ and that is where I think I did not understand the previous computation. I know that the answer has to be $x^2+3$ or $x^2+2$ but I do not know how to get it. Should I have to divide $x^{24}-1$ by $x^4+1$ and following with this strategy to find the gcd or is there any easier way to find it?
Thank you so much!
 A: $$(x^{20}-x^{16}+x^{12}-x^8+x^4-1)(x^4+1)=(x^{24}-1)$$
A: More general, $x^4\equiv -1\pmod{x^4+1}$, so $x^{4k+r}\equiv (-1)^{k}x^r\pmod{x^4+1}$, so $x^{24}\equiv (-1)^6=1\pmod{x^4+1}$.
The same trick works for dividing $x^{24}-1$ by $x^4+2$:
$$x^4\equiv -2\pmod{x^4+2}\\
x^{24}\equiv (-2)^6\pmod{x^4+2}\\
x^{24}-1\equiv 3\pmod{x^4+2}$$
More generally, over $\mathbb F_q$, $$x^{q-1}\equiv a\pmod{x^{q-1}-a}\\
x^{q^2-1}=a^{q+1}=a^2\pmod{x^{q-1}-a}
$$
So $x^{q^2-1}-1$ is divisible by $x^{q-1}-a$ iff $a=\pm 1$. Otherwise, the two are relatively prime.
A: Here’s another technique, which even though of limited utility, works beautifully and quickly when it works at all.
You are asking for roots of $X^4=-1$ over $\Bbb F_5$, and the degree of the extension that one of them (and hence all) generates. But these are the primitive eighth roots of unity, and you need to know the degree of the smallest extension of $\Bbb F_5$ that contains these. In other words, you are looking for the first $n$ such that $8|(5^n-1)$. Answer is $n=2$, of course, thus each such eighth root generates $\Bbb F_{25}$, and each is merely quadratic over $\Bbb F_5$, so that $X_4+1$ necessarily factors into two quadratics. (The method doesn’t give the factorization.)
But it works equally well for $X^4+2$, since now you’re talking about fourth roots of $3$, which in turn is a primitive fourth root of unity. So roots of $X^4+2$ are sixteenth roots of unity, and the first $n$ such that $16|(5^n-1)$ is $n=4$. Irreducible.
