Primitive roots of 1 modulo a prime

Hi Sir,

I wanted to make sure what i was doing was right. The question says find the primitive roots of the primes 5 and 7.

For 5

1^4=1 \mod 5

2^4=1 \mod 5

3^4=1 \mod 5

4^4=1 \mod 5

so i obtained 1,2,3,4.

For 7

1^6=1 \mod 7

2^6=1 \mod 7

3^6=1 \mod 7

4^6=1 \mod 7

5^6=1 \mod 7

6^6=1 \mod 7

so obtained 1,2,3,4,5,6.

Is this the correct way to do this? I was getting confused between primitive roots and residue classes. Residue classes are just the numbers co-prime to O(5-1)=O(4), which is 3,1 and for O(7-1)=O(6) is 5,1.

Am i right or on the wrong track?


Reply: You are getting several notions mixed up. If you fix a modulus m, then the
residue classes modulo m are represented by all the possible remainders after dividing by m, and hence, are

\{ \bar{0}, \bar{1}, \ldots, \overline{m-1}\}.

For example, the residue classes modulo 6 are

\{ \bar{0}, \bar{1}, \bar{2}, \bar{3}, \bar{4}, \bar{5}\}.

On the other hand, the residue classes that are *invertible* modulo m are represented by the classes \bar{a} where a is coprime to m. For example, the residue classes that are invertible modulo 6 are

\{ \bar{1}, \bar{5}\}.

If m happens to be a prime, then all non-zero residue classes are invertible modulo m.

Fermat’s little theorem says that if m is a prime, then for any non-zero residue class \bar{a}, we have


So *all* the non-zero residue classes are (m-1) -th roots of 1 modulo m. However, the *primitive* roots of 1 are those for which



\bar{a}^i\neq \bar{1}

for any i<m-1. That is, these are the residue classes that have exact order m-1 with respect to multiplication. For example, modulo 5, \bar{1} is a 4-th root of 1, but definitely not a primitive fourth root. Similarly,


but also


So \bar{4} fails as well to be a primitive 4-th root of 1. However, you can check that \bar{2} and \bar{3} *are* primitive 4-th roots of 1.

Now go back to your investigation of the primitive 6-th roots of 1 modulo 7.

By the way, your question indicates that you should read the definitions and examples in the notes more carefully several times.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: