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