<s>[INST] 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!
 [/INST] 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.
</s>