# Understanding Primitive roots

I am trying to find a single primitive root modulo $11$. The definition in my textbook says "Let $a$ and $n$ be relatively prime integers with ($a \neq 0$) and $n$ positive. Then the least positive integer $x$ such that $a^x\equiv1\pmod{\! n}$ is called the order of $a$ modulo $n$ and is denoted by $\text{ord}_{n}a$".

So what I don't understand is how I can find a single primitive root modulo $11$ if I am not also given $a$.

Or is it that maybe I understand things after all since $2$ is a primitive root modulo $11$ since $2^{10} \equiv \phi(11)\equiv 10\pmod{\! 11}$ and $2$ is a generator for the group $\mathbb{Z}/11\mathbb{Z}$?

In any case, I am confused since I need to find a second primitive root modulo $11$ and I'm not sure how to do that other than by guessing and checking $a^{10}$ for $a \in \{3,4,5,6,7,8,9,10\}$. Any help would be appreciated.

• It's not true that $2^{10}\equiv \phi(11)\equiv 10\pmod{\! 11}$. We have $2^{10}\equiv 1\pmod{\! 11}$ by little Fermat. When we know that, we'll know $2$ is a primitive root mod $11$ iff we know $2^k\not\equiv 1\pmod{\! 11}$ for $k\in\{1,2,\ldots,9\}$. We can shorten the process of checking $\{1,2,\ldots,9\}$ by checking only $\{2,5\}$, i.e. $\left\{\frac{10}{5},\frac{10}{2}\right\}$, instead. – user26486 Jun 18 '15 at 11:23
• $a^{10}$ is always $1$ for any $a\in\{1,2,\ldots, 10\}$ by little Fermat, so no need to check $a\in\{3,4,\ldots, 10\}$ at all. The real problem here is to prove $a^k$ is never $1$ for $k\in\{1,2,\ldots,9\}$. – user26486 Jun 18 '15 at 11:34

Be careful not to mix up the additive group of $\mathbb Z/11 \mathbb Z = \{0, 1, \ldots, 10\}$ with the multiplicative group of $(\mathbb Z/11 \mathbb Z)^* = \{1, \ldots, 10\}$. Since the latter group has order $10$, it follows by Lagrange's Theorem that each non-identity element must have an order of either $2$, $5$, or $10$. So for each candidate $g \in \{2, \ldots, 10\}$, it suffices to verify that $g^2, g^5 \neq 1$ in order to prove that $g$ is a primitive root. Indeed, notice that: $$10^2 = 1 = 3^5 = 4^5 = 5^5 = 9^5$$ So none of these $5$ candidate are primitive roots. On the other hand: $$2^5 = 6^5 = 7^5 = 8^5 = 10 \neq 1$$ and: $$(2^2, 6^2, 7^2, 8^2) = (4, 3, 5, 9)$$ none of which are $1$. Hence, we have found all $\phi(10) = 4$ primitive roots.

One cannot in general find primitive roots without trying, but it usually does not take many trials. (If your prime $p$ is so large that factoring $p-1$ is a problem, then just testing whether a given number is a primitive root may be a stumbling block, but that is a different matter.)

In the given case, you can just write down the powers of $2$ modulo $11$, to find the sequence $1,2,4,8,5,10,9,7,3,6,1$, which returns to its starting value only after seeing all nonzero classes modulo$~11$, so indeed the class $[2]$ of $2$ is a primitive element for this field; the first trial succeeds. Once you've got this, you know that $i\mapsto[2^i]$ (the brackets meaning the class modulo$~11$ induces a group isomorphism from the additive group $\Bbb Z/10\Bbb Z$ to the multiplicative group $(\Bbb Z/11\Bbb Z)^\times$; the other generators of the latter group correspond to the generators of $\Bbb Z/10\Bbb Z$, which are the classes relatively prime to$~10$: for $3$ one gets $[2^3]=[8]$, for $7$ one gets $[2^7]=[7]$, and for $9$ one gets $[2^9]=[6]$.

• It is enough to show $2\not\equiv 0,\, 2^2\not\equiv 1,\, 2^5\not\equiv 1\pmod{\! 11}$ and you don't need to find all the powers of $2$ mod $11$. See my answer. – user26486 Jun 18 '15 at 16:43
• @user26486 Yes I know (that's why I mentioned factoring $p-1$ in my first paragraph). But for this small example there is hardly any benefit from using that theory, while it is instructive to see at a glance that indeed all nonzero classes arise as powers of $2$. Moreover the other primitive elements are obtained as powers of $2$ that are not the ones relevant to checking that $2$ is primitive, so you'd have to separately compute those powers afterwards anyway. – Marc van Leeuwen Jun 19 '15 at 14:01

Using only simple language:

$a$ is a primitive root mod $p$ iff $\text{ord}_p (a)=p-1$. Also,

$$\text{ord}_p(a)=k\iff (a^k\equiv 1\!\!\pmod{\! p}\ \text{ and }\ q\mid k\,\Rightarrow\, a^{k/q}\not\equiv 1\!\!\pmod{\! p})$$

$a\not\equiv 0$ is a primitive root mod $p$ iff

$$q\mid p-1\,\Rightarrow\, a^{(p-1)/q}\not\equiv 1\!\!\pmod{\! p}$$

$a\not\equiv 0$ is a primitive root mod $11$ iff

$$a^5\not\equiv 1,\, a^2\not\equiv 1\pmod{\! 11}$$

None of $1,3,4,5,9,10$ is a primitive root mod $11$, because

$$1^2\equiv 3^5\equiv 4^5\equiv 5^5\equiv (-2)^5\equiv (-1)^2\equiv 1\pmod{\! 11}$$

$\{2,6,7,8\}$ is the set of primitive roots mod $11$, because $$2^{5}\not\equiv 1,\, 2^2\not\equiv 1,\,(-5)^5\not\equiv 1,\, (-5)^2\not\equiv 1,\, (-4)^5\not\equiv 1,$$

$$(-4)^2\not\equiv 1,\, (-3)^5\not\equiv 1,\, (-3)^2\not\equiv 1\pmod{\! 11}$$

You just need to verify the candidates to primitive roots one by one in order, the candidates are all the numbers $k\in[1,n-1]$, where $n$ is the "modulo n" in your question.

The way of knowing which ones are primitive roots is by calculating the following congruences for each one of the candidates $k$:

$k^1 \pmod{n}$

$k^2\pmod{n}$

...

$k^{n-1}\pmod{n}$

This is mod your number $n$, in this case $\pmod{11}$.

If all the congruences of $k$ as above are not $0$ and different, so the total of non-zero congruences of $k$ are exactly $\varphi(n)$ and different between them, which is equivalent to say that the period of $k^j \pmod n$ is exactly $\varphi(n)$, then $k$ is a primitive root modulo $n$.

So in your case, verify each number in $[1,10]$, for instance $2$, and then calculate $2^1,2^2..2^{10}$ and for each value calculate mod $11$, if no one of those congruences is $0$ and all of them are different then $2$ is a primitive root.

Indeed, the primitive roots modulo $11$ are $\{2,6,7,8\}$. Here is an online calculator.

• You're not looking for whether the powers of $k$ are congruent to $0$ modulo $n$. For example, $k=1$ always satisfies $k^j\not\equiv1\pmod n$, but $1$ is not a primitive root when $n\ge3$. – Greg Martin Jun 18 '15 at 6:08
• @GregMartin fixed, I forgot to mention that they must be different so the period of $k^j \pmod n$ is exactly $(n-1)$ – iadvd Jun 18 '15 at 6:13
• Still not quite right: the period should be $\phi(n)$, not $n-1$. Example: $n=9$. – Greg Martin Jun 18 '15 at 19:48
• @GregMartin done! again thank you for taking time for those corrections, I apologize. :) – iadvd Jun 18 '15 at 23:41
• No problem, we're all here to learn, and help perfect one another's contributions :) – Greg Martin Jun 19 '15 at 19:17