using primitive roots and index to solve congruences

The aim of the following example is to illustrate how to use primitive rootsMathworldPlanetmath and the index of an integer to solve seemingly complicated congruencesMathworldPlanetmath.

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


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 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 x12
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 entry):

x 1 2 3 4 5 6 7 8 9 10 11 12
indx 12 1 4 2 9 5 11 3 8 10 7 6

Now we can use the properties of index to solve the equation 7x105mod13. By taking indices on both sides we obtain


and so indxind5-ind79-1110mod12. The equivalence 10indx10mod12 implies 5indx5mod6 and hence indx1mod6. Lifting this solution to modulo 12 we obtain indx1 or 7 modulo 12, and by the table of indices, x2 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