What is $(x^7-x)mod(x^6-3)$ equal to?

Question

I'm trying to use Rabins test for irreducibility over finite fields , but in part of the test you need to calculate $gcd(f,x^{p^{n_i}}-xmodf)$ where in my case p=7 and n=6,3,2 as I'm testing if $f(x)=x^6-3$ is irreducible over GF(7).

My trouble is I don't know how to calculate this modulo, I know how to do it for integers and I know that in my case it implies that $x^6=3$. But after this i'm stuck.

could anyone work me through how to find what $(x^7-x)mod(x^6-3)$ is equal to ?

Also is Rabins test a good go to for testing if a polynomial is irreducible over a finite field ? Or is there perhaps less cumbersome methods for higher degree's of f(x) where degree f(x)>3 and so doesn't strictly need to be factored into linear polynomials in order to be irreducible ? (just suggestions would suffice )

Answer 1

Division algorithm:

$$x^7 - x = (x^6 - 3) (x) + (2x)$$

and this is valid because $\deg (2x) < \deg (x^6 - 3)$

So the remainder is $2x$.

Answer 2

Note that

$$x^7-x=x(x^6-3)+2x$$