2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – user26486 Jun 18 '15 at 11:23
  • $\begingroup$ $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\}$. $\endgroup$ – user26486 Jun 18 '15 at 11:34
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – user26486 Jun 18 '15 at 16:43
  • $\begingroup$ @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. $\endgroup$ – Marc van Leeuwen Jun 19 '15 at 14:01
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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$. $\endgroup$ – Greg Martin Jun 18 '15 at 6:08
  • $\begingroup$ @GregMartin fixed, I forgot to mention that they must be different so the period of $k^j \pmod n$ is exactly $(n-1)$ $\endgroup$ – iadvd Jun 18 '15 at 6:13
  • $\begingroup$ Still not quite right: the period should be $\phi(n)$, not $n-1$. Example: $n=9$. $\endgroup$ – Greg Martin Jun 18 '15 at 19:48
  • $\begingroup$ @GregMartin done! again thank you for taking time for those corrections, I apologize. :) $\endgroup$ – iadvd Jun 18 '15 at 23:41
  • 1
    $\begingroup$ No problem, we're all here to learn, and help perfect one another's contributions :) $\endgroup$ – Greg Martin Jun 19 '15 at 19:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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