Orders of primitive roots

Question

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.

Answer 1

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

Answer 2

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<d$ which satisfy this (by definition), we get $\phi(d)$ elements of order $d$. I leave the rigorous proof as an exercise.

Answer 3

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$

Answer 4

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.