1
$\begingroup$

So a primitive root/element $g$$\pmod{n}$ is an element in $\mathbb Z^*_{n}$ such that when $g$ is raised to each element in $\mathbb Z^*_{n}$ it generates the whole set of $\mathbb Z^*_{n}$

But the way to find a primitive root seems totally unrelated to me. You try $2$, then $3$, etc until you get a number that has no $\equiv 1\pmod{n}$

Why is an element $g$ not primitive$\pmod{n}$ if $g^\frac{n-1}{f} \equiv 1\pmod{n}$ for some prime factor $f$ of $n-1$? I don't see the connection

  • 1
    Yes, $n$ is prime - I should've mentioned (and used $p$ instead)2012-11-09

3 Answers 3

1

By definition, a primitive element $\rm\,g\,$ of a group $\rm\: G\:$ is an element that generates the whole group, i.e. $\rm\,\langle g\rangle = G.\:$ But if $\rm\:g^n = 1\:$ for $\rm\:n < |G|\:$ then $\,\rm|\langle g\rangle| \le n < |G|\:\Rightarrow\: \langle g\rangle \ne G,\:$ therefore we conclude that $\rm\:g\:$ is not a generator.

1

if $g^{\frac{n-1}f} \equiv 1$, then $\{g^1,g^2,g^3,g^4,\ldots\} = \{g^1,g^2,g^3,g^4,\ldots,g^{\frac{n-1}f}\}$, which has at most $\frac{n-1}f$ elements (because we don't know if they are all distinct or not).

Now (I guess you wanted $n$ to be prime), $\mathbb Z_n^*$ has $n-1$ elements, and $\frac{n-1}f < n-1$, so $\{g^1,g^2,g^3,g^4,\ldots\}$ is a strict subset (subgroup even) of $\mathbb Z_n^*$, which precisely means that $g$ is not a primitive element.

1

As you said, the powers of a primitive root $g$ needs to generate all of $(\mathbb{Z}/n\mathbb{Z})^{\times}$. For simplifying the discussion, let me assume that $n$ is a prime. Then there are $n-1$ elements in the group.

The order of an element is the smallest positive exponent $x$ such that $a^x \equiv 1$. What that means is that as you take powers of $a$ repeatedly, they will all be different until you reach $a^x \equiv 1$ in which the cycle repeats itself. You can try a few examples and you will see that the set generated in this way will have precisely $x$ elements, where $x$ is the order of the generator.

If your element $g$ does not have order $n-1$ then how can it possibly generate a group which has $n-1$ elements?

The reason we try $\frac{n-1}{f}$ for the order is because the order of each element must divide the order of the group (which is $n-1$). From Fermat's little theorem, we know that $a^{p-1} \equiv 1 \pmod p$ Now suppose $a$ has order $x$. We shall show that $x\mid p-1$. Write $p - 1 = nx + r$ using the division algorithm for $0\le r < x$. Then $a^{p-1} = a^{nx+r} \equiv a^{nx}a^r \equiv a^r\equiv 1\pmod p$ But $x$ is the smallest positive exponent such that $a^x \equiv 1$ and $r$ is strictly smaller. This must mean that $r$ is $0$.

  • 0
    That took me a while to understand but I finally get it now. Thanks heaps2012-11-09