Primitive roots - Algebra, CSIR-NET Mathematical Sciences | Mathematics for IIT JAM, GATE, CSIR NET, UGC NET PDF Download

Let  be a positive integer. A primitive root mod n is an integer g such that every integer relatively prime to n is congruent to a power of g mod n. That is, the integer g is a primitive root (mod n) if for every number a relatively prime to n there is an integer z such that a ≡ (g^z (mod n)).

When primitive roots exist, it is often very convenient to use them in proofs and explicit constructions; for instance, if p is an odd prime and g is a primitive root mod p, the quadratic residues mod p are precisely the even powers of the primitive root. Primitive roots are also important in cryptological applications involving the discrete log problem, most notably the Diffie-Hellman key exchange protocol.

Terminology and a formal definition

Define

So Z*_n has φ(n) elements, where φ is Euler's totient function.

Background and motivation

The set  has an important property: it is closed under multiplication mod n. That is, if  and c is the positive integer less than n which is congruent to ab mod n, then  as well. This is because ab and n have no common factor (by unique factorization), and so c and n have no common factor either (because if d|c and d|n, then d|ab as well, because ab = c +nx some integer x)

This property, together with other basic properties of multiplication mod n, imply that  is a group under multiplication.

For any element a ∈ Z*_n, consider the sequence of its powers  . All of the powers of a are in the finite set , so the sequence of powers a of  repeats eventually. In fact, Euler's theorem implies that it repeats with period 

So another characterization of primitive roots in terms of this sequence is: Primitive roots are the elements  for which the sequence of powers of a has minimum period  
 

Existence of primitive roots

Primitive roots do not necessarily exist mod n for any n. Here is a complete classification:

Finding primitive roots

The proof of the theorem (part of which is presented below) is essentially non-constructive: that is, it does not give an effective way to find a primitive root when it exists. Once one primitive root g has been found, the others are easy to construct: simply take the powers g^a where a is relatively prime to  But finding a primitive root efficiently is a difficult computational problem in general.

There are some special cases when it is easer to find them; for example:

For instance, this shows that 2 is a primitive root mod 83.

Applications

When there is a primitive root g mod n, the elements of  Z*_n can be written as  Multiplying two elements corresponds to adding their exponents mod That is, the multiplicative arithmetic in Z*_n reduces to additive arithmetic in 

Here is another problem where it can help to write the elements of Z*_p as powers of a primitive root.

Partial proof of the theorem

One half of this theorem is not hard to prove: Suppose where a and b are relatively prime and > 3. Suppose x is relatively prime to ab. Then since  mod a and  mod b, it follows that

But  are both even, so their lcm is strictly less than their product. So the order of x is strictly less than  So there is no primitive root mod ab.

The only n that cannot be written in this way are  and higher powers of 2. But for any odd x,

which can be proved by the LTE lemma (or by induction). Since  there is no primitive root mod

Some of the proof of the other direction can be found in the wiki on orders.