Solve the equation x^6 = 1 in F_19.
Do not use brute force. I know I can just substitute in x=0 ... x=18, but rather than doing that, I would like to know a more clever method so I can solve such equations easily in general.
You can solve this problem using a primitive element of F_19. Every element of F_p has what we call an order, i.e. the least power you need to raise it to get 1. The order of any element has to be a divisor of p-1. This follows directly from a theorem of Lagrange in group theory, but we can give a self contained sketch of a proof here. First we recall Fermat's little theorem:
For every element x not equal to zero we have that:
x^(p-1) = 1
A simple sketch of a proof goes as follows. Consider the product of all the nonzero elements
S = 1*2*3*...*(p-1)
Then consider the product obtained by multiplying each factor in here by x:
Q = (1*x)*(2*x)*(3*x)*...*((p-1)*x)
Each of the factors r*x in Q appear as factors in S and vice versa, so Q is in fact the same as S, it is just that the factors as written down in the equation for Q simply appear in a different order. But we can also take out a factor x from each of the factors r*p in Q to write it as:
Q = x^(p-1) ...
We give a fully self contained solution which includes a sketch of a derivation of Fermat's little theorem and all other techniques one needs to use to find all solutions.