Mathematics Exam  >  Mathematics Notes  >  Mathematics for IIT JAM, GATE, CSIR NET, UGC NET  >  Primitive roots - Algebra, CSIR-NET Mathematical Sciences

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 ≡ (gz (mod n)).

EXAMPLE

2 is a primitive root mod 5, because for every number, a relatively prime to 5 there is an. 2z ≡ a.  All the numbers relatively prime to 5 are 1, 2, 3, 4, and each of these (mod 5) is itself (for instance 2 (mod 5) = 2).

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

 

EXAMPLE

4 is not a primitive root mod 5, because for every number relatively prime to 5 (again: 1, 2, 3, 4) there is not a power of 4 that is congruent. Powers of 4 (mod 5) are only congruent to 1 or 4. There is no power of 4 that is congruent to 2 or 3. 

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


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

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

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

DEFINATION

primitive root mod n is an element g ∈ Z*n whose powers generate all of Z*n. That is, every element b ∈ Z*n can be written as gx mod n, for some integer x.


Background and motivation

The set Primitive roots - Algebra, CSIR-NET Mathematical Sciences | Mathematics for IIT JAM, GATE, CSIR NET, UGC NET has an important property: it is closed under multiplication mod n. That is, if Primitive roots - Algebra, CSIR-NET Mathematical Sciences | Mathematics for IIT JAM, GATE, CSIR NET, UGC NET and c is the positive integer less than n which is congruent to ab mod n, then Primitive roots - Algebra, CSIR-NET Mathematical Sciences | Mathematics for IIT JAM, GATE, CSIR NET, UGC NET 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 Primitive roots - Algebra, CSIR-NET Mathematical Sciences | Mathematics for IIT JAM, GATE, CSIR NET, UGC NET is a group under multiplication.

For any element a ∈ Z*n, consider the sequence of its powers Primitive roots - Algebra, CSIR-NET Mathematical Sciences | Mathematics for IIT JAM, GATE, CSIR NET, UGC NET . All of the powers of a are in the finite set Primitive roots - Algebra, CSIR-NET Mathematical Sciences | Mathematics for IIT JAM, GATE, CSIR NET, UGC NET, so the sequence of powers a of  repeats eventually. In fact, Euler's theorem implies that it repeats with period Primitive roots - Algebra, CSIR-NET Mathematical Sciences | Mathematics for IIT JAM, GATE, CSIR NET, UGC NET

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

So another characterization of primitive roots in terms of this sequence is: Primitive roots are the elements Primitive roots - Algebra, CSIR-NET Mathematical Sciences | Mathematics for IIT JAM, GATE, CSIR NET, UGC NET for which the sequence of powers of a has minimum period Primitive roots - Algebra, CSIR-NET Mathematical Sciences | Mathematics for IIT JAM, GATE, CSIR NET, UGC NET 
 

Example

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

The powers of 1 are 1,1,1,... The order of 1 is 1.

The powers of 2 are 2,4,8,7,5,1,... The order of 2 is 6.

The powers of 4 are 4,7,1,... The order of 4 is 3.

The powers of 5 are 5,7,8,4,2,1,... The order of 5 is 6.

The powers of 7 are 7,4,1,.. The order of 7 is 3.

The powers of 8 are 8,1,... The order of 8 is 2.

So the primitive roots mod 9 are 2 and 5.


Existence of primitive roots

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

THEOREM

There are primitive roots mod n if and only if n = 1,2,4,pk or 2pk where p is an odd prime.


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 ga where a is relatively prime to Primitive roots - Algebra, CSIR-NET Mathematical Sciences | Mathematics for IIT JAM, GATE, CSIR NET, UGC NET 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:

EXANPLE

Suppose p is a prime such that 2p + 1 is also prime. (Such p are called Sophie Germain primes.) Show that if p ≡ 1 mod 4, then 2 is a primitive root mod 2p +1.

Solution: The point is that the list of possible orders of elements of  Primitive roots - Algebra, CSIR-NET Mathematical Sciences | Mathematics for IIT JAM, GATE, CSIR NET, UGC NET  is very short: the order of 2 divides Primitive roots - Algebra, CSIR-NET Mathematical Sciences | Mathematics for IIT JAM, GATE, CSIR NET, UGC NET so it is either Primitive roots - Algebra, CSIR-NET Mathematical Sciences | Mathematics for IIT JAM, GATE, CSIR NET, UGC NET It can't be 1 or 2 so we only need to rule out P. But Primitive roots - Algebra, CSIR-NET Mathematical Sciences | Mathematics for IIT JAM, GATE, CSIR NET, UGC NET  is the Legendre symbol; this is by Euler's criterion. But by the second supplement to quadratic reciprocity, Primitive roots - Algebra, CSIR-NET Mathematical Sciences | Mathematics for IIT JAM, GATE, CSIR NET, UGC NET

So the only remaining possibility is that the order of 2 mod 2p +1 is 2p. 


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 Primitive roots - Algebra, CSIR-NET Mathematical Sciences | Mathematics for IIT JAM, GATE, CSIR NET, UGC NET Multiplying two elements corresponds to adding their exponents mod Primitive roots - Algebra, CSIR-NET Mathematical Sciences | Mathematics for IIT JAM, GATE, CSIR NET, UGC NETThat is, the multiplicative arithmetic in Z*n reduces to additive arithmetic in Primitive roots - Algebra, CSIR-NET Mathematical Sciences | Mathematics for IIT JAM, GATE, CSIR NET, UGC NET

EXAMPLE

Let k be an integer and p an odd prime number. How many nonzero kth powers are there mod p?

The question certainly depends on the relationship between k and p. When k = 2 the answer is p-1/2 (see quadratic residues), but when k = p - 1 the answer is 1 (by Fermat's little theorem).

As an illustration, take Primitive roots - Algebra, CSIR-NET Mathematical Sciences | Mathematics for IIT JAM, GATE, CSIR NET, UGC NET Then it's easy to check that g = 2 is a primitive root mod p. The ninth powers mod p are Primitive roots - Algebra, CSIR-NET Mathematical Sciences | Mathematics for IIT JAM, GATE, CSIR NET, UGC NET but we can consider the exponents mod 12 because Primitive roots - Algebra, CSIR-NET Mathematical Sciences | Mathematics for IIT JAM, GATE, CSIR NET, UGC NET So we get Primitive roots - Algebra, CSIR-NET Mathematical Sciences | Mathematics for IIT JAM, GATE, CSIR NET, UGC NET

so there are four 9th powers mod 13. The exponents are multiples of 3, which is gcd. (9,13 -1). There are 13 - 1/3 = 4 of these.

In general, since every nonzero element of Zp can be written as ga mod p for some integer x, the equation xk ≡ y mod p can be rewritten Primitive roots - Algebra, CSIR-NET Mathematical Sciences | Mathematics for IIT JAM, GATE, CSIR NET, UGC NET mod p. Because g is a primitive root, this happens if and only if Primitive roots - Algebra, CSIR-NET Mathematical Sciences | Mathematics for IIT JAM, GATE, CSIR NET, UGC NET

So the question becomes: as a ranges over Zp-1, how many values can ak mod p-1 take on? In fact, the extended Euclidean algorithm implies that Primitive roots - Algebra, CSIR-NET Mathematical Sciences | Mathematics for IIT JAM, GATE, CSIR NET, UGC NET  is the set of multiples of gcd Primitive roots - Algebra, CSIR-NET Mathematical Sciences | Mathematics for IIT JAM, GATE, CSIR NET, UGC NET

There are exactly Primitive roots - Algebra, CSIR-NET Mathematical Sciences | Mathematics for IIT JAM, GATE, CSIR NET, UGC NET

such values, so this is the answer.


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: SupposePrimitive roots - Algebra, CSIR-NET Mathematical Sciences | Mathematics for IIT JAM, GATE, CSIR NET, UGC NET where a and b are relatively prime and > 3. Suppose x is relatively prime to ab. Then since Primitive roots - Algebra, CSIR-NET Mathematical Sciences | Mathematics for IIT JAM, GATE, CSIR NET, UGC NET mod a and Primitive roots - Algebra, CSIR-NET Mathematical Sciences | Mathematics for IIT JAM, GATE, CSIR NET, UGC NET mod b, it follows that Primitive roots - Algebra, CSIR-NET Mathematical Sciences | Mathematics for IIT JAM, GATE, CSIR NET, UGC NET

But Primitive roots - Algebra, CSIR-NET Mathematical Sciences | Mathematics for IIT JAM, GATE, CSIR NET, UGC NET are both even, so their lcm is strictly less than their product. So the order of x is strictly less than Primitive roots - Algebra, CSIR-NET Mathematical Sciences | Mathematics for IIT JAM, GATE, CSIR NET, UGC NET So there is no primitive root mod ab.

The only n that cannot be written in this way are Primitive roots - Algebra, CSIR-NET Mathematical Sciences | Mathematics for IIT JAM, GATE, CSIR NET, UGC NET and higher powers of 2. But for any odd x,

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

which can be proved by the LTE lemma (or by induction). Since Primitive roots - Algebra, CSIR-NET Mathematical Sciences | Mathematics for IIT JAM, GATE, CSIR NET, UGC NET there is no primitive root mod Primitive roots - Algebra, CSIR-NET Mathematical Sciences | Mathematics for IIT JAM, GATE, CSIR NET, UGC NET

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

The document Primitive roots - Algebra, CSIR-NET Mathematical Sciences | Mathematics for IIT JAM, GATE, CSIR NET, UGC NET is a part of the Mathematics Course Mathematics for IIT JAM, GATE, CSIR NET, UGC NET.
All you need of Mathematics at this link: Mathematics
556 videos|198 docs

FAQs on Primitive roots - Algebra, CSIR-NET Mathematical Sciences - Mathematics for IIT JAM, GATE, CSIR NET, UGC NET

1. What are primitive roots in algebra?
Ans. In algebra, primitive roots are integers that generate all the possible residue classes modulo a given prime number. Specifically, a primitive root modulo n is an integer g such that every number coprime to n can be expressed as a power of g modulo n.
2. How can one determine if an integer is a primitive root modulo a prime number?
Ans. To determine if an integer g is a primitive root modulo a prime number n, one needs to check if g^k is congruent to 1 modulo n for any positive integer k less than n-1. If this condition holds true, then g is not a primitive root. Otherwise, if no such k exists, then g is a primitive root modulo n.
3. What is the significance of primitive roots in number theory?
Ans. Primitive roots play a significant role in number theory as they help in understanding the properties of prime numbers and the structure of the set of residue classes modulo a prime. They are used in various cryptographic algorithms, prime factorization algorithms, and in solving Diophantine equations.
4. Can a composite number have primitive roots modulo it?
Ans. No, a composite number does not have primitive roots modulo it. Primitive roots only exist modulo prime numbers. This is because composite numbers have a certain structure that does not allow for the generation of all possible residue classes in the same way as prime numbers.
5. Are all prime numbers guaranteed to have primitive roots?
Ans. Yes, every prime number has at least one primitive root modulo it. This is known as the Primitive Root Theorem. In fact, most prime numbers have multiple primitive roots. The existence of primitive roots modulo prime numbers is a fundamental property of number theory and plays a crucial role in various mathematical and cryptographic applications.
Explore Courses for Mathematics exam
Signup for Free!
Signup to see your scores go up within 7 days! Learn & Practice with 1000+ FREE Notes, Videos & Tests.
10M+ students study on EduRev
Related Searches

CSIR NET

,

Extra Questions

,

shortcuts and tricks

,

CSIR-NET Mathematical Sciences | Mathematics for IIT JAM

,

study material

,

Previous Year Questions with Solutions

,

MCQs

,

Free

,

UGC NET

,

GATE

,

UGC NET

,

Summary

,

video lectures

,

CSIR-NET Mathematical Sciences | Mathematics for IIT JAM

,

Primitive roots - Algebra

,

GATE

,

Sample Paper

,

Viva Questions

,

CSIR NET

,

past year papers

,

mock tests for examination

,

Primitive roots - Algebra

,

ppt

,

Important questions

,

Exam

,

CSIR NET

,

pdf

,

Semester Notes

,

CSIR-NET Mathematical Sciences | Mathematics for IIT JAM

,

practice quizzes

,

Primitive roots - Algebra

,

Objective type Questions

,

GATE

,

UGC NET

;