Order and Primitive Elements

The Order of a Unit

Recall that ${\mathbb{Z}}_n^{\ast }$ is the set of units of ${\mathbb{Z}}_n$; the elements $a\in {\mathbb{Z}}_n$ with $\gcd (a,n)=1$, i.e. exactly the elements that have a multiplicative inverse. Recall also Euler's Theorem: for any $a\in {\mathbb{Z}}_n^{\ast }$,

$$a^{\varphi (n)}=1\text{ in }{\mathbb{Z}}_n.$$

So some power of every unit eventually equals $1$; it is natural to ask for the first time this happens.

Basically, the order of $a$ measures how long the powers $a,a^2,a^3,\dots$ take to first return to $1$; after that point the powers just repeat the same cycle forever. Other notation for the order of $a\in {\mathbb{Z}}_n^{\ast }$ includes ${\mathrm{ord}}_{{\mathbb{Z}}_n}(a)$, $o_n(a)$ and $|a|$.

Be careful: "order" can mean something different depending on context; the order of a finite field $F$ sometimes refers to the number of elements in $F$.

It is important to note that the order is only defined for units; if $\gcd (a,n)\ne 1$, then no power of $a$ ever reaches $1$.

Example. Explain why ${\mathrm{ord}}_{15}(6)$ does not exist.
Notice that $\gcd (6,15)=3\ne 1$, so $6\notin {\mathbb{Z}}_{15}^{\ast }$. Watching the powers directly,

$$\begin{array}{rl}{6}^2& =36\\ & =2\times 15+6\\ & =6\text{ in }{\mathbb{Z}}_{15},\end{array}$$

so every power of $6$ collapses back to $6$ itself and can never equal $1$. More generally, $3\mid 6^k$ for every $k\in {\mathbb{Z}}^{+}$, but $3\nmid (15m+1)$ for any $m$; so $6^k=1$ in ${\mathbb{Z}}_{15}$ is impossible. Therefore ${\mathrm{ord}}_{15}(6)$ does not exist; always check that $a$ is a unit before talking about its order.

Example. Find the orders of each of the elements in ${\mathbb{Z}}_7^{\ast }$.
We previously found the power table for ${\mathbb{Z}}_7^{\ast }$:

Reading along each row until the first $1$ appears,

$$\begin{array}{rl}{\mathrm{ord}}_7(1)& =1,\\ {\mathrm{ord}}_7(2)& =3,\\ {\mathrm{ord}}_7(3)& =6,\\ {\mathrm{ord}}_7(4)& =3,\\ {\mathrm{ord}}_7(5)& =6,\\ {\mathrm{ord}}_7(6)& =2.\end{array}$$

Notice how every order that shows up ($1,2,3$ and $6$) is a divisor of $6=\varphi (7)$; this is not a coincidence, as we are about to see.

Order Divides the Totient

Before the main theorem, we need a small lemma that describes exactly which powers of a unit equal $1$.

Proof. Let $d={\mathrm{ord}}_n(a)$.
($\Leftarrow$) Suppose $d\mid k$; then $k=dq$ for some $q\in \mathbb{N}$, so

$$\begin{array}{rl}{a}^k& =a^{dq}\\ & =(a^d{)}^q\\ & =1^q\\ & =1\text{ in }{\mathbb{Z}}_n.\end{array}$$

($\Rightarrow$) Suppose $a^k=1$. By the Division Theorem we can write $k=qd+r$ with $0\le r<d$, so

$$\begin{array}{rl}1& =a^k\\ & =(a^d{)}^q{a}^r\\ & =1^q{a}^r\\ & =a^r.\end{array}$$

But $d$ is the smallest positive exponent giving $1$, and $r<d$; the only way out is $r=0$. Hence $k=qd$; that is, $d\mid k$. $■$

Basically, the powers of $a$ hit $1$ at $d,2d,3d,\dots$ and nowhere else; the sequence of powers is periodic with period exactly ${\mathrm{ord}}_n(a)$. Since $a$ is invertible, $a^i=a^j$ (for $i\ge j$) is the same as $a^{i-j}=1$, which gives a fact worth boxing:

$$\boxed{a^i=a^j\text{ in }{\mathbb{Z}}_n⟺i\equiv j(\mathrm{mod}{\mathrm{ord}}_n(a)).}$$

This theorem is what makes computing orders fast. Instead of grinding through $a,a^2,a^3,\dots$ one power at a time, you only ever need to test the exponents $k$ that divide $\varphi (n)$; the order must be one of those divisors, and it is the smallest one that works.

Example. Find ${\mathrm{ord}}_{15}(7)$.
First, $\varphi (15)=\varphi (3)\varphi (5)=2\times 4=8$, so ${\mathrm{ord}}_{15}(7)\in \{1,2,4,8\}$. Testing the divisors in increasing order,

$$\begin{array}{rl}{7}^1& =7\ne 1,\\ 7^2& =49\\ & =3\times 15+4\\ & =4\ne 1,\\ 7^4& =(7^2{)}^2\\ & =4^2\\ & =16\\ & =1\text{ in }{\mathbb{Z}}_{15}.\end{array}$$

Therefore, ${\mathrm{ord}}_{15}(7)=4$.

Example. Find ${\mathrm{ord}}_{18}(5)$.
Here $\varphi (18)=\varphi (2)\varphi (9)=1\times 6=6$, so the order is one of $1,2,3,6$. Testing,

$$\begin{array}{rl}{5}^1& =5\ne 1,\\ 5^2& =25\\ & =7\ne 1,\\ 5^3& =5\times 7\\ & =35\\ & =17\\ & =-1\ne 1\text{ in }{\mathbb{Z}}_{18}.\end{array}$$

Every proper divisor of $6$ has failed, so the order is forced to be $\varphi (18)$ itself; we do not even need to compute $5^6$, since Euler's Theorem already guarantees $5^6=1$. Therefore, ${\mathrm{ord}}_{18}(5)=6$.

Notice how landing on $-1$ was a bonus; once you see $a^k=-1$, you immediately know $a^{2k}=1$, and that no smaller multiple of $k$ can give $1$ along that chain. Keep an eye out for $-1$; it saves a lot of arithmetic.

Example. Find $7^{2026}$ in ${\mathbb{Z}}_{15}$.
From earlier, ${\mathrm{ord}}_{15}(7)=4$, so the powers of $7$ repeat with period $4$; we only care about $2026$ modulo the order:

$$\begin{array}{rl}2026& =4\times 506+2,\\ 7^{2026}& =(7^4{)}^{506}\times 7^2\\ & =1^{506}\times 4\\ & =4\text{ in }{\mathbb{Z}}_{15}.\end{array}$$

Therefore, $7^{2026}=4$ in ${\mathbb{Z}}_{15}$. You could also have reduced the exponent modulo $\varphi (15)=8$ (Euler), but the order gives the tightest possible reduction. Reduce the exponent modulo the order, never modulo $n$; $2026\equiv 1(\mathrm{mod}15)$ tells you nothing about $7^{2026}$.

Primitive Elements

Since the order of a unit always divides $\varphi (n)$, the largest an order can possibly be is $\varphi (n)$ itself. The units that actually achieve this maximum get a special name.

Basically, a primitive element is a unit whose powers take the longest possible route before cycling back to $1$; as we will see shortly, its powers visit every unit along the way.

Example. The primitive elements of ${\mathbb{Z}}_7^{\ast }$ are $3$ and $5$, since we saw in the order table that ${\mathrm{ord}}_7(3)={\mathrm{ord}}_7(5)=6=\varphi (7)$.

Example. What are the primitive elements of ${\mathbb{Z}}_6^{\ast }$?
Here ${\mathbb{Z}}_6^{\ast }=\{1,5\}$ and $\varphi (6)=2$. Clearly ${\mathrm{ord}}_6(1)=1\ne 2$, and

$$\begin{array}{rl}{5}^2& =25\\ & =4\times 6+1\\ & =1\text{ in }{\mathbb{Z}}_6,\end{array}$$

so ${\mathrm{ord}}_6(5)=2=\varphi (6)$. Therefore, the only primitive element of ${\mathbb{Z}}_6^{\ast }$ is $5$.

Example. What are the primitive elements of ${\mathbb{Z}}_8^{\ast }$?
Here ${\mathbb{Z}}_8^{\ast }=\{1,3,5,7\}$ and $\varphi (8)=4$. Squaring each unit,

$$\begin{array}{rl}{3}^2& =9=1\text{ in }{\mathbb{Z}}_8,\\ 5^2& =25=1\text{ in }{\mathbb{Z}}_8,\\ 7^2& =49=1\text{ in }{\mathbb{Z}}_8,\end{array}$$

so every unit other than $1$ has order $2$, and ${\mathrm{ord}}_8(1)=1$; no element has order $\varphi (8)=4$. Therefore, ${\mathbb{Z}}_8^{\ast }$ has no primitive elements. Not every ${\mathbb{Z}}_n^{\ast }$ has a primitive element; never assume one exists without checking.

Primitive Elements as Generators

Proof. Each power $a^k$ is a product of units and hence a unit, so $⟨a⟩\subseteq {\mathbb{Z}}_n^{\ast }$. Now suppose two of the listed powers were equal; say $a^i=a^j$ with $0\le i<j\le \varphi (n)-1$. Since $a$ is invertible, we can multiply both sides by $(a^i{)}^{-1}$ to get

$$\begin{array}{rl}{a}^{j-i}& =1,\text{where }0<j-i<\varphi (n).\end{array}$$

But $a$ is primitive, so ${\mathrm{ord}}_n(a)=\varphi (n)$; there is no positive exponent smaller than $\varphi (n)$ giving $1$, which is a contradiction. Hence the powers $a^0,a^1,\dots ,a^{\varphi (n)-1}$ are $\varphi (n)$ distinct elements of ${\mathbb{Z}}_n^{\ast }$; and since ${\mathbb{Z}}_n^{\ast }$ only has $\varphi (n)$ elements in total, the two sets must be equal. $■$

Basically, a primitive element generates the whole unit group; every single unit mod $n$ is some power of $a$. This is exactly why primitive elements are so useful: one element single-handedly produces everything.

For example, the first six powers of either primitive element of ${\mathbb{Z}}_7^{\ast }$ sweep out all of ${\mathbb{Z}}_7^{\ast }$; all six units appear in the rows for $3$ and $5$:

Contrast this with $2$, which is not primitive; its powers $2,4,1,2,4,1,\dots$ only ever produce $\{1,2,4\}$, i.e. $⟨2⟩\ne {\mathbb{Z}}_7^{\ast }$.

Multiplication with Primitive Elements

In ${\mathbb{Z}}_p$ for any prime $p$, we can use the fact that the powers of a primitive element generate ${\mathbb{Z}}_p^{\ast }$ to build a method for multiplication in ${\mathbb{Z}}_p$ that is very time-efficient for very large $p$.

Suppose we know $a$ is a primitive element of ${\mathbb{Z}}_p^{\ast }$ and have recorded the powers of $a$ in a lookup table. Then we can multiply two numbers $x,y\in {\mathbb{Z}}_p^{\ast }$ as follows:

• Use the lookup table to find $i$ and $j$ such that $x=a^i$ and $y=a^j$ in ${\mathbb{Z}}_p$.
• Calculate $(i+j)\mathrm{mod}(p-1)$.
• Use the lookup table to find $a^{(i+j)\mathrm{mod}(p-1)}=xy$ in ${\mathbb{Z}}_p$.

The reason we reduce the exponent mod $p-1$ is that ${\mathrm{ord}}_p(a)=\varphi (p)=p-1$, so by our boxed fact the exponents only matter modulo $p-1$. The efficiency of this method for large $p$ (and $x,y$) comes from the fact that the only calculation required is addition, which is computationally much cheaper than multiplication; this is basically how logarithm tables worked before calculators, with $i$ playing the role of ${\log }_a(x)$.

Example. Given the powers of $2$ in ${\mathbb{Z}}_{11}$, find $5\times 10$ and $7\times 9$ in ${\mathbb{Z}}_{11}$.

For $5\times 10$: from the table, $5=2^4$ and $10=2^5$, so

$$\begin{array}{rl}5\times 10& =2^4\times 2^5\\ & =2^{(4+5)\mathrm{mod}10}\\ & =2^9\\ & =6\text{ in }{\mathbb{Z}}_{11}.\end{array}$$

For $7\times 9$: from the table, $7=2^7$ and $9=2^6$, so

$$\begin{array}{rl}7\times 9& =2^7\times 2^6\\ & =2^{13\mathrm{mod}10}\\ & =2^3\\ & =8\text{ in }{\mathbb{Z}}_{11}.\end{array}$$

As a sanity check, $50=4\times 11+6$ and $63=5\times 11+8$; both answers agree with direct computation.

The lookup table also lets you run this machine in reverse, which is exactly a discrete logarithm.

Example. Find all $x\in \mathbb{Z}$ such that $2^x=7$ in ${\mathbb{Z}}_{11}$.
From the table, $2^7=7$; and since the powers of $2$ repeat with period ${\mathrm{ord}}_{11}(2)=10$, we have $2^x=2^7$ if and only if $x\equiv 7(\mathrm{mod}10)$. Therefore, the solutions are exactly $x\equiv 7(\mathrm{mod}10)$.

Example. Solve $x^4=5$ in ${\mathbb{Z}}_{11}$.
Every non-zero element of ${\mathbb{Z}}_{11}$ is a power of the primitive element $2$, so write $x=2^t$; from the table $5=2^4$. The equation becomes

$$\begin{array}{rl}{2}^{4t}& =2^4\\ 4t& \equiv 4(\mathrm{mod}10)\\ 2t& \equiv 2(\mathrm{mod}5)\\ t& \equiv 1(\mathrm{mod}5),\end{array}$$

where we divided the congruence (and the modulus) by $\gcd (4,10)=2$, then multiplied by the inverse of $2$ mod $5$. So $t\in \{1,6\}$ modulo $10$, giving

$$\begin{array}{rl}x& =2^1=2,\\ x& =2^6=9\text{ in }{\mathbb{Z}}_{11}.\end{array}$$

Checking: $9^2=81=4$ and $4^2=16=5$ in ${\mathbb{Z}}_{11}$. Therefore, the solutions are $x=2$ and $x=9$. Notice how the primitive element converted a nasty power equation into a linear congruence in the exponent; this is the standard trick for equations of the form $x^k=b$ in ${\mathbb{Z}}_p$.

Which Unit Groups Have Primitive Elements

We saw that ${\mathbb{Z}}_8^{\ast }$ has no primitive element, so existence is a genuine question. Fortunately there is a complete answer.

The proof of this one is apparently quite complicated so it's omitted for this course; these questions are just pattern matching against the list. In particular, every prime modulus has a primitive root, which is why the multiplication trick above always works in ${\mathbb{Z}}_p$.

Example. Do each of the following groups of units have primitive elements?

• ${\mathbb{Z}}_{10}^{\ast }$: here $10=2\times 5=2p^k$ with $p=5$, $k=1$; so yes. (Indeed $3$ works: its powers in ${\mathbb{Z}}_{10}$ are $3,9,7,1$, so ${\mathrm{ord}}_{10}(3)=4=\varphi (10)$.)
• ${\mathbb{Z}}_{35}^{\ast }$: here $35=5\times 7$ is a product of two distinct odd primes, which is not on the list; so no.
• ${\mathbb{Z}}_{343}^{\ast }$: here $343=7^3=p^k$; so yes.

Example. Show directly that ${\mathbb{Z}}_{12}^{\ast }$ has no primitive element.
Since $12=2^2\times 3$ is not of any of the allowed forms, the theorem says no; but it is worth seeing this happen by hand. We have ${\mathbb{Z}}_{12}^{\ast }=\{1,5,7,11\}$ and $\varphi (12)=4$, and

$$\begin{array}{rl}{5}^2& =25=1\text{ in }{\mathbb{Z}}_{12},\\ 7^2& =49=1\text{ in }{\mathbb{Z}}_{12},\\ 11^2& =121=1\text{ in }{\mathbb{Z}}_{12},\end{array}$$

so every unit has order at most $2<4$. This is the same behaviour as ${\mathbb{Z}}_8^{\ast }$; everything squares to $1$, so no single element can generate all four units.

Finding a Primitive Element

In general, there is no known efficient method to find a primitive element of ${\mathbb{Z}}_n^{\ast }$. The method we use (inefficient, but fine by hand) is:

• Choose $a$ to be a small element of ${\mathbb{Z}}_n^{\ast }$, taking candidates from the list of numbers that are not pure powers: $2,3,5,6,7,10,11,\dots$ in order.
• For each prime divisor $p_i$ of $\varphi (n)$, compute $a^{\varphi (n)/p_i}$ in ${\mathbb{Z}}_n$.
• If $a^{\varphi (n)/p_i}\ne 1$ in ${\mathbb{Z}}_n$ for all prime divisors $p_i$ of $\varphi (n)$, then (and only then) $a$ is a primitive element of ${\mathbb{Z}}_n^{\ast }$.

The reason this works comes back to order dividing the totient. If ${\mathrm{ord}}_n(a)\ne \varphi (n)$, then ${\mathrm{ord}}_n(a)$ is a proper divisor of $\varphi (n)$; its prime factorisation must be missing at least one copy of some prime divisor $p_i$ of $\varphi (n)$, so ${\mathrm{ord}}_n(a)\mid \varphi (n)/p_i$, and hence $a^{\varphi (n)/p_i}=1$ by the Lemma. Conversely, if $a$ is primitive then no exponent smaller than $\varphi (n)$ can give $1$. So testing just those few exponents $\varphi (n)/p_i$ detects primitivity exactly; you never have to check every divisor of $\varphi (n)$.

We skip pure powers like $4,8,9$ in the candidate list because they can never succeed after their base has failed; if $4=2^2$ were primitive, then ${\mathrm{ord}}_n(2)$ would already have to be $\varphi (n)$ (a power of $2$ can't cycle for longer than $2$ does), so $2$ would have been primitive first.

Example. Find a primitive element of ${\mathbb{Z}}_{31}^{\ast }$.
Here $\varphi (31)=30=2\times 3\times 5$, so the exponents to test are

$$\frac{30}{2}=15,\frac{30}{3}=10,\frac{30}{5}=6.$$

Candidate $a=2$:

$$\begin{array}{rl}{2}^5& =32\\ & =1\text{ in }{\mathbb{Z}}_{31},\\ 2^{15}& =(2^5{)}^3\\ & =1\text{ in }{\mathbb{Z}}_{31},\end{array}$$

so $2$ fails the test (in fact ${\mathrm{ord}}_{31}(2)=5$) and is not primitive.
Candidate $a=3$: first note $3^5=243=7\times 31+26=26=-5$ in ${\mathbb{Z}}_{31}$, then

$$\begin{array}{rl}{3}^6& =3^5\times 3\\ & =-15\\ & =16\ne 1,\\ 3^{10}& =(3^5{)}^2\\ & =(-5{)}^2\\ & =25\ne 1,\\ 3^{15}& =3^{10}\times 3^5\\ & =25\times (-5)\\ & =-125\\ & =-1\ne 1\text{ in }{\mathbb{Z}}_{31},\end{array}$$

since $-125+4\times 31=-1$. All three tests pass; therefore $3$ is a primitive element of ${\mathbb{Z}}_{31}^{\ast }$. Notice how writing $26$ as $-5$ made every one of these computations painless; working with small negative representatives is almost always faster than working with large positive ones.

Finding All Primitive Elements

Once you have found one primitive element, you get all the others essentially for free.

Proof. Let $g=\gcd (k,\varphi (n))$ and let $m={\mathrm{ord}}_n(a^k)$. Since ${\mathrm{ord}}_n(a)=\varphi (n)$, the Lemma from earlier gives

$$(a^k{)}^m=a^{km}=1⟺\varphi (n)\mid km.$$

Dividing both $\varphi (n)$ and $k$ by $g$, this is equivalent to $\frac{\varphi (n)}{g}\mid \frac{k}{g}m$; and since $\gcd \left(\frac{\varphi (n)}{g},\frac{k}{g}\right)=1$, this happens exactly when $\frac{\varphi (n)}{g}\mid m$. The smallest positive such $m$ is $\frac{\varphi (n)}{g}$, so

$${\mathrm{ord}}_n(a^k)=\frac{\varphi (n)}{\gcd (k,\varphi (n))},$$

which equals $\varphi (n)$ precisely when $\gcd (k,\varphi (n))=1$. $■$

The exact same argument works with $\varphi (n)$ replaced by the order of any unit, giving a formula that is genuinely worth memorising:

$$\boxed{{\mathrm{ord}}_n(a^k)=\frac{{\mathrm{ord}}_n(a)}{\gcd (k,{\mathrm{ord}}_n(a))}.}$$

Basically, raising $a$ to the power $k$ shrinks its cycle by exactly the factor $\gcd (k,{\mathrm{ord}}_n(a))$; if $k$ shares no factors with the order, the cycle length is untouched.

$$\boxed{\text{If }{\mathbb{Z}}_n^{\ast }\text{ has a primitive element, it has exactly }\varphi (\varphi (n))\text{ of them.}}$$

This matches everything we have seen so far: ${\mathbb{Z}}_6^{\ast }$ has $1$ primitive element ($5$) and $\varphi (\varphi (6))=\varphi (2)=1$, while ${\mathbb{Z}}_7^{\ast }$ has $2$ primitive elements ($3$ and $5$) and $\varphi (\varphi (7))=\varphi (6)=2$.

Example. Given $2$ is a primitive element of ${\mathbb{Z}}_9^{\ast }$, find all the primitive elements of ${\mathbb{Z}}_9^{\ast }$.
Here $\varphi (9)=9-3=6$, and ${\mathbb{Z}}_6^{\ast }=\{1,5\}$; so by the corollary, the primitive elements are exactly $2^1$ and $2^5$:

$$\begin{array}{rl}{2}^1& =2,\\ 2^5& =32\\ & =3\times 9+5\\ & =5\text{ in }{\mathbb{Z}}_9.\end{array}$$

Therefore, the primitive elements of ${\mathbb{Z}}_9^{\ast }$ are $2$ and $5$; as a check, $\varphi (\varphi (9))=\varphi (6)=2$ elements, as expected.

Example. Find all primitive elements of ${\mathbb{Z}}_{31}^{\ast }$.
From the previous section, $3$ is a primitive element of ${\mathbb{Z}}_{31}^{\ast }$ and $\varphi (31)=30$. The units mod $30=2\times 3\times 5$ are the numbers coprime to $2$, $3$ and $5$:

$${\mathbb{Z}}_{30}^{\ast }=\{1,7,11,13,17,19,23,29\},$$

which has $\varphi (30)=\varphi (2)\varphi (3)\varphi (5)=1\times 2\times 4=8$ elements; so there are exactly $8$ primitive elements, namely $3^k$ for each $k\in {\mathbb{Z}}_{30}^{\ast }$. First tabulate the powers of $3$ up to $3^{15}=-1$:

The exponents up to $15$ can be read straight off the table, and since $3^{15}=-1$, every later power is just the negative of an earlier one; $3^{15+j}=-3^j$:

$$\begin{array}{rl}{3}^1& =3,\\ 3^7& =17,\\ 3^{11}& =13,\\ 3^{13}& =24,\\ 3^{17}& =-3^2=-9=22,\\ 3^{19}& =-3^4=-19=12,\\ 3^{23}& =-3^8=-20=11,\\ 3^{29}& =-3^{14}=-10=21\text{ in }{\mathbb{Z}}_{31}.\end{array}$$

Therefore, the primitive elements of ${\mathbb{Z}}_{31}^{\ast }$ are

$$\{3,11,12,13,17,21,22,24\},$$

and there are $8=\varphi (\varphi (31))$ of them, as expected.

Example. Construct the full order table for ${\mathbb{Z}}_{13}^{\ast }$ and hence find all primitive elements of ${\mathbb{Z}}_{13}^{\ast }$.
The lazy way is to compute the whole $12\times 12$ power table; the smart way is to find one primitive element and then use the boxed formula for ${\mathrm{ord}}_n(a^k)$.

First, $\varphi (13)=12=2^2\times 3$, so the prime divisors of $\varphi (13)$ are $2$ and $3$ and we test the exponents $\frac{12}{2}=6$ and $\frac{12}{3}=4$. Trying $a=2$:

$$\begin{array}{rl}{2}^4& =16\\ & =3\ne 1,\\ 2^6& =64\\ & =12\\ & =-1\ne 1\text{ in }{\mathbb{Z}}_{13},\end{array}$$

so $2$ is a primitive element of ${\mathbb{Z}}_{13}^{\ast }$. Its powers are:

Every unit $a\in {\mathbb{Z}}_{13}^{\ast }$ is $2^k$ for exactly one $k\in \{1,\dots ,12\}$, and

$${\mathrm{ord}}_{13}(2^k)=\frac{12}{\gcd (k,12)}.$$

For instance $9=2^8$, so ${\mathrm{ord}}_{13}(9)=\frac{12}{\gcd (8,12)}=\frac{12}{4}=3$; checking, $9^3=729=56\times 13+1=1$ in ${\mathbb{Z}}_{13}$. Running through every $k$ gives the complete order table:

The primitive elements are the units of order $12$; therefore the primitive elements of ${\mathbb{Z}}_{13}^{\ast }$ are

$$\{2,6,7,11\},$$

and indeed $\varphi (\varphi (13))=\varphi (12)=4$ of them. Notice also how every order in the table is a divisor of $12$, and for each divisor $d$ of $12$ the number of elements of order $d$ is exactly $\varphi (d)$:

$$\begin{array}{rlrl}d=1& :\{1\},& \varphi (1)& =1,\\ d=2& :\{12\},& \varphi (2)& =1,\\ d=3& :\{3,9\},& \varphi (3)& =2,\\ d=4& :\{5,8\},& \varphi (4)& =2,\\ d=6& :\{4,10\},& \varphi (6)& =2,\\ d=12& :\{2,6,7,11\},& \varphi (12)& =4.\end{array}$$

This pattern holds whenever a primitive element exists; it is a handy sanity check that your order computations are consistent, since the counts have to add up to $\varphi (n)$.