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