Recipe

Determine or list the generators of Z_n

Use when: you're asked whether one specific $k$ generates $\mathbb{Z}_n$ , or asked for the complete list of generators, or asked only how many there are

Goal: a definitive answer, generator or not for one $k$ , the full list, or the exact count, matching what was actually asked

Taught in Generators of Z_n

Quick recipe

Decide what's actually being asked
For a single k, compute gcd(k, n) and read off the answer directly
For the full list, test gcd(k, n) for every k from 1 to n-1 and keep the ones equal to 1
For the count only, compute phi(n) directly, no listing required

1
Read the question carefully: it might ask about one specific element, the complete list of generators, or just the count of how many exist -- each needs a different amount of work.

Example

"Does $8$ generate $\mathbb{Z}_{12}$ ?" is a single-element test, so Step 2. "List every generator of $\mathbb{Z}_8$ " asks for the full list, so Step 3. "How many generators does $\mathbb{Z}_9$ have?" asks only for the count, so Step 4.
- asked about ONE specific $k$ — continue to Step 2.
- asked to LIST every generator — continue to Step 3.
- asked only for the COUNT — continue to Step 4.
Why: computing one gcd is genuinely less work than listing every element of $\{1,\ldots,n-1\}$ or computing $\varphi(n)$ , so knowing which question was asked avoids doing work nobody needed.
2
Compute $\gcd(k,n)$ with the Euclidean algorithm, then compare it to $1$ .

Example

$k=8$ , $n=12$ : $\gcd(8,12)=4$ . Since $4\ne1$ , $8$ does not generate $\mathbb{Z}_{12}$ ; its subgroup has order $12/4=3$ .
- $\gcd(k,n)=1$ — $k$ generates $\mathbb{Z}_n$ .
- $\gcd(k,n)=d>1$ — $k$ does not generate $\mathbb{Z}_n$ ; its own subgroup has order $n/d$ .
Why: $k$ generates $\mathbb{Z}_n$ exactly when $|\langle k\rangle|=n$ , i.e. $n/\gcd(k,n)=n$ , which happens exactly when $\gcd(k,n)=1$ .
3
Compute $\gcd(k,n)$ for each candidate in turn, then collect only the values of $k$ where the gcd came out to exactly $1$ .

Example

$n=10$ : $\gcd(k,10)=1$ for $k=1,3,7,9$ ; every other $k$ from $1$ to $9$ shares a factor with $10$ .

Why: this is the single-element test from Step 2, applied once to every candidate instead of just one.
4
Apply the prime-power and product formulas from the last section to $n$ itself; no candidate ever needs testing.

Example

$n=9$ : $\varphi(9)=9-3=6$ , so $\mathbb{Z}_9$ has $6$ generators, without naming any of them.

Why: the number of generators of $\mathbb{Z}_n$ is $\varphi(n)$ by definition, since the generators are exactly the integers coprime to $n$ .

Common mistakes

Falling back on a full orbit listing ( $k, 2k, 3k, \ldots$ ) when a single gcd computation already settles whether $k$ generates.
Accepting a gcd that's small but not exactly $1$ as good enough -- only $\gcd(k,n)=1$ counts.
Computing $\varphi(n)$ when the question actually asked for the generators themselves, not just their count.
Reporting the subgroup order $n/\gcd(k,n)$ as if it answered a different question than the one asked.