# using primitive roots and index to solve congruences

For this example, let $p=13$ and let us attempt to solve

 $7x^{10}\equiv 5\mod 13.$

Since every prime has a primitive root, we can easily find one. In particular, the number $2$ is a primitive root for $p=13$. Indeed, the powers of $2$ are the following modulo $13$:

$x$ $x^{2}$ $x^{3}$ $x^{4}$ $x^{5}$ $x^{6}$ $x^{7}$ $x^{8}$ $x^{9}$ $x^{10}$ $x^{11}$ $x^{12}$
$2$ $4$ $8$ $3$ $6$ $12$ $11$ $9$ $5$ $10$ $7$ $1$

The table above allows us to build a table of indices with base $2$ (for the definition of index and its properties which will be used below, see http://planetmath.org/node/PropertiesOfTheIndexOfAnIntegerWithRespectToAPrimitiveRootthis entry):

 $x$ $\operatorname{ind}x$ $1$ $2$ $3$ $4$ $5$ $6$ $7$ $8$ $9$ $10$ $11$ $12$ $12$ $1$ $4$ $2$ $9$ $5$ $11$ $3$ $8$ $10$ $7$ $6$

Now we can use the properties of index to solve the equation $7x^{10}\equiv 5\mod 13$. By taking indices on both sides we obtain

 $\operatorname{ind}(7x^{10})\equiv\operatorname{ind}7+10\operatorname{ind}x% \equiv\operatorname{ind}5\mod 12$

and so $\operatorname{ind}x\equiv\operatorname{ind}5-\operatorname{ind}7\equiv 9-11% \equiv 10\mod 12$. The equivalence $10\operatorname{ind}x\equiv 10\mod 12$ implies $5\operatorname{ind}x\equiv 5\mod 6$ and hence $\operatorname{ind}x\equiv 1\mod 6$. Lifting this solution to modulo $12$ we obtain $\operatorname{ind}x\equiv 1$ or $7$ modulo $12$, and by the table of indices, $x\equiv 2$ or $11$ modulo $13$ are the unique solutions of the congruence.

Title using primitive roots and index to solve congruences UsingPrimitiveRootsAndIndexToSolveCongruences 2013-03-22 16:20:58 2013-03-22 16:20:58 alozano (2414) alozano (2414) 4 alozano (2414) Example msc 11-00 PrimitiveRoot Congruence PolynomialCongruence