Find all the primitive roots of $13$
My attempt:
Since that $13$ is a prime I need to look for $g$ such that $g^{13-1}\equiv 1\pmod{13}$
There are $\phi(12)=4$ classes modulo $12$
how can I find the classes?
$\endgroup$ 74 Answers
$\begingroup$Clearly, $2$ is a primitive root $\pmod{13}$
as $2^n\not\equiv1\pmod{13}$ for $1\le n<12$
Now use ord$_ma=d, $ord$_m(a^k)=\dfrac{d}{(d,k)}$ (Proof @Page#95)
Here $d=\phi(13)=?$ and we need ord$_m(a^k)=d$ which needs $(d,k)=1$
$\endgroup$ $\begingroup$Take all the numbers less than and coprime to 13 . 1 to 12 are coprime to 13 . Check $1^{13-1}\equiv 1\pmod{13}$ $2^{13-1}\equiv 1\pmod{13}$ And so on upto $12^{13-1}\equiv 1\pmod{13}$ Every 1 to 12 which is $\equiv 1\pmod{13}$ is the required answer . $edit $: the power should be the least power which gives the value $\equiv 1\pmod{13}$
$\endgroup$ 6 $\begingroup$Primes have not just one primitive root, but many. So you find the first primitive root by taking any number, calculating its powers until the result is 1, and if p = 13 you must have 12 different powers until the result is 1 to have a primitive root.
If you tried a number a that wasn't a primitive root then don't try it's powers but some other number.
Once you have one primitive root, call it g. $g^2$ is not a primitive root because $(g^2)^6 = g^{12} = 1$. Same for the powers 3, 4, 6, 8, 9, 10. $g^5$, $g^7$, $g^11$ are the other primitive roots.
$\endgroup$ $\begingroup$My quick & dirty method was to note that $13-1=12$ has prime factors $2,3$ & quickly find squares and cubes of a numbers, since those cannot be primitive roots, and not checking those which have already turned up. Any indication of a "short cycle" (like $5$) also gets discarded immediately.
$2: 2^2 \equiv 4, 2^3 \equiv 8 \\ 3: 3^2 \equiv 9, 3^3 \equiv 1 \text{(discard all)}\\ 5: 5^2 \equiv 12 \equiv -1 \text{(discard all)} \\ 6: 6^2 \equiv 10, 6^3 \equiv 8 \\ 7: 7^2 \equiv 10, 7^3 \equiv 5 \\ 11: 11^2 \equiv 4, 11^3 \equiv 5 $
leaving $\{2,6,7,11\}$ as the primitive roots which is in accordance with the expectation of $\phi(12)=4$ roots (and also the knowledge that for each primitive root $g \bmod p$, $-g$ is a primitive root iff $p \equiv 1 \bmod 4$).
$\endgroup$
