# Orders of primitive roots

So I'm working through a textbook and the question asks:

Consider the prime $$p =13$$. For each divisor $$d = 1,2,3,4,6,12$$ of $$12= p-1$$, mark which of the natural numbers in the set $$\{1,2,3,4,5,6,7,8,9,10,11,12\}$$ have order $$d$$.

I know that the order is when: $$a^n \equiv 1 \mod n$$ given $$(a,n)=1$$.

From my understanding, from Fermat's Little Theorem or an extension of Euler's Theorem, since $$13$$ is a prime and all the natural numbers in that set is relatively prime to $$13.$$ I can use the formula: $$a^{\phi(n)} \equiv 1 \mod n$$, since $$p$$ is prime, I know $$\phi(p)= p-1$$, therefore $$\phi(13)=12$$.

Therefore all the orders of all the elements would be 12 not the other divisors. Is this line of reasoning correct or am I misunderstanding the question?

Thank you for any guidance.

• the order of an element $a$ is the least positive integer $n$ such that $a^n\equiv1$ Aug 27, 2019 at 0:24
• Consider the number 1. While $1^{12} \equiv 1$ mod $13$, $1^1 \equiv 1$ mod $13$ Aug 27, 2019 at 0:25
• @ZacharyHunter I actually discovered that as well but couldn't find an example for the other numbers. Aug 27, 2019 at 0:31
• @Safder: for example $3^3=27=2\times13+1\equiv1\mod13$ Aug 27, 2019 at 1:13

The reasoning is off a little. You can only conclude the order of each element divides $$12$$.

Thus you still have to check the orders. Note: only $$\varphi (12)=4$$ of them will have order $$12$$. These are the so-called primitive roots mod $$13$$.

In fact, there will be $$\varphi (d)$$ elements of order $$d$$ for each $$d$$ dividing $$12$$.

• Okay so in this case I should check if all the divisors and then pick the lowest one as the order. How would you go about this problem given a much larger number say $p=101$ then $\phi(101)$ has a large number of divisors? Also, could you further explain the last statement about the number of elements? Aug 27, 2019 at 0:35
• Yeah. It's well known in case $n$ is $1,2,4$, a power of an odd prime or twice a power of an odd prime, the multiplicative group $U(n)$ is cyclic. The statement about the number of elements of order $d$ can be understood by taking a generator, and considering what happens when you raise it to various powers. Recall that $g^k$ has order $\dfrac {\mid g\mid}{\operatorname {gcd}(\mid g\mid,k)}$.
– user403337
Aug 27, 2019 at 0:50
• For the first question, the better you are at modular arithmetic, the easier it will be.
– user403337
Aug 27, 2019 at 0:54
• Perfect, makes sense. A little beyond the scope of what I've learned thus far but I'll definitely look into it. Thanks! Aug 27, 2019 at 1:00

If $$a$$ is a primitive root of $$n$$ where $$\phi(n)=kd$$, consider the order of $$a^k$$. Also consider $$a^{mk}$$ where $$(m,d)=1$$. Since by definition there are $$\phi(d)$$ numbers $$m which satisfy this (by definition), we get $$\phi(d)$$ elements of order $$d$$. I leave the rigorous proof as an exercise.

• Just to ensure my understanding of a primitive root is clear, a is a primitive root given then the order of a is $\phi(p) = p-1$. So for the case mentioned above, for 1 since the order is 1, it is not a primitive root. Am I correct? Aug 27, 2019 at 0:49
• yes, correct. $1 \equiv a^{\phi(n)}$ mod $n$ however, and $\phi(n) = \phi(n)\cdot 1$, so in a round about manner we can use this to conclude that 1 has order 1. Aug 27, 2019 at 0:52
• Awesome, thank you. Aug 27, 2019 at 1:00

You are wrong about the definition of the order of an element. In particular the order of a mod n is the smallest positive $$k$$ such that $$a^k\equiv 1 mod(n)$$.

For example the order of $$3$$ $$mod(13)$$ is $$3$$, in fact $$3^3 \equiv 27 \equiv 1 mod(13)$$ and $$3^1 \equiv 3 mod(13)$$, $$3^2 \equiv 9 mod(13)$$.

Another example is the order of $$4$$ $$mod(13)$$, that is $$6$$, in fact $$4^6 \equiv 2^{12} \equiv 1 mod(13)$$ and $$4^1 \equiv 4 mod(13)$$, $$4^2 \equiv 3 mod(13)$$, $$4^3 \equiv 12 mod(13)$$ and $$4^4 \equiv 9 mod(13)$$.

I can not check $$4^5$$ because the order of an element, mod n, certainly divided $$\phi(n)$$, in particular $$5$$ doesn't divided $$\phi(13)=12$$

• Isn't $2^6 mod 13 = 12$ therefore how can it be the order because it is not congruent to the $1 mod 13$? Aug 27, 2019 at 0:59
• yes sorry, i will change my example @Safder Aug 27, 2019 at 1:01

Since $$1^n=1$$ and $$-1^2n=1$$ exist, all we can conclude is that that the exponent that creates remainder 1 has all it's multiples turn out to produce 1. This, and using the known highest possible minimal exponent, says if 12 creates 1(given); either one of it's divisors creates 1, or no exponent before 6 can create -1. Attempting it, we get the following:$$1^1\equiv 1\\2^{12}\equiv 1\\3^3\equiv 1\\4^6\equiv 1\\5^4\equiv 1\\6^{12}\equiv 1\\7^{12}\equiv 1\\8^4\equiv 1\\9^6\equiv 1\\10^6\equiv 1\\11^{12}\equiv 1\\12^2\equiv 1$$ All mod 13.

You'll note if we needed values above 1, there is almost a perfect symmetry. This comes from equivalent naming in modular arithmetic, and $$(-x)^{2n}=x^{2n}$$ So in cases where an even order occurs on one, only if -1 is in the powers will the negative create a lower order. odd powers being equivalent to opposite signs of each other.

• @quid how can this be edited before posted ?
– user645636
Oct 31, 2019 at 23:26