Explore BrainMass

Find all solutions of x^16 = 1 Mod 19

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.

Solution Preview

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) ...

Solution Summary

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.