# using primitive roots and index to solve congruences

The aim of the following example is to illustrate how to use primitive roots and the index of an integer to solve seemingly complicated 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