Explore BrainMass

Explore BrainMass

    Find all solutions of x^16 = 1 Mod 19

    This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

    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.

    © BrainMass Inc. brainmass.com October 10, 2019, 1:29 am ad1c9bdddf

    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.