## 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

$\bar{a}^{m-1}=\bar{1}.$

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}^{m-1}=\bar{1}$

but

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

for any $i. 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,

$\bar{4}^4=\bar{1},$

but also

$\bar{4}^2=1.$

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.