Understanding Primitive roots

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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

Answer 4

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