# 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

$$7{x}^{10}\equiv 5mod13.$$ |

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$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ | $10$ | $11$ | $12$ |
---|---|---|---|---|---|---|---|---|---|---|---|---|

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

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

$$\mathrm{ind}(7{x}^{10})\equiv \mathrm{ind}7+10\mathrm{ind}x\equiv \mathrm{ind}5mod12$$ |

and so $\mathrm{ind}x\equiv \mathrm{ind}5-\mathrm{ind}7\equiv 9-11\equiv 10mod12$. The equivalence $10\mathrm{ind}x\equiv 10mod12$ implies $5\mathrm{ind}x\equiv 5mod6$ and hence $\mathrm{ind}x\equiv 1mod6$. Lifting this solution to modulo $12$ we obtain $\mathrm{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 |
---|---|

Canonical name | UsingPrimitiveRootsAndIndexToSolveCongruences |

Date of creation | 2013-03-22 16:20:58 |

Last modified on | 2013-03-22 16:20:58 |

Owner | alozano (2414) |

Last modified by | alozano (2414) |

Numerical id | 4 |

Author | alozano (2414) |

Entry type | Example |

Classification | msc 11-00 |

Related topic | PrimitiveRoot |

Related topic | Congruence |

Related topic | PolynomialCongruence |