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 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 $7x^{10}\equiv 5mod13$. By taking indices on both sides we obtain

$$\mathrm{ind}(7x^{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