Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
Is $n$ prime? Not clear, but the emphasis on $n-1$ seems to imply you might be intending it to be. –  Thomas Andrews Nov 9 '12 at 15:46
    
Yes, $n$ is prime - I should've mentioned (and used $p$ instead) –  Arvin Nov 9 '12 at 16:03
add comment

3 Answers

up vote 1 down vote accepted

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$.

share|improve this answer
    
That took me a while to understand but I finally get it now. Thanks heaps –  Arvin Nov 9 '12 at 16:20
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.