Primitive sets $\bmod n$

Question

Let $[a,b] \bmod n$ be a "pairwise" primitive root (or in general the set $[a,a_2,a_3..a_t]$ would be called a primitive set) such that for all integers $k$ that $\gcd(k,n)=1$, there exists integers $i$ and $j$ such that $a^ib^j = k \pmod n$.

For example, $[2,6] \bmod 7$ would be an example of a pairwise primitive root since $2^i6^j = k \pmod 7$ for all $k$ that $\gcd(k,7)=1$ despite $2$ and $6$ not being primitive roots $\pmod 7$.

It is known $n=24$ has no primitive roots. There are also no pairwise primitive roots $[a,b]$. The smallest primitive set would be $[5,7,13]$.

1) Do all numbers $n$ have a primitive set of at most three integers $[a,b,c]$? If not, counterexample?

2) What is the criteria for $n$ not to have a pairwise primitive root $[a,b]$?

Answer 1

The more standard terminology for this concept is that the set $\{a_1,a_2,\dots,a_t\}$ generates the multiplicative group $(\Bbb Z/n\Bbb Z)^\times$. This is only possible if that multiplicative group can be written as the direct product of at most $t$ cyclic groups. (This is not trivially true, but is a consequence of the classification of finite abelian groups.) Equivalently, this is possible if the length of the invariant factor decomposition of $(\Bbb Z/n\Bbb Z)^\times$ is at most $t$.

It is possible to show that the length of the invariant factor decomposition of $(\Bbb Z/n\Bbb Z)^\times$ is $$ \begin{cases} \omega(n), &\text{if $n$ is odd}, \\ \omega(n)-1, &\text{if $2\mid n$ and $4\nmid n$}, \\ \omega(n), &\text{if $4\mid n$ and $8\nmid n$}, \\ \omega(n)+1, &\text{if } 8\mid n, \end{cases} $$ where $\omega(n)$ is the number of distinct prime divisors of $n$.

In particular, the smallest integer $n$ whose multiplicative group cannot be generated by $3$ elements is $n=8\times3\times5=120$.

The integers that can be generated by two elements are precisely those that are:

• a product of at most two odd prime powers;
• twice a product of at most two odd prime powers;
• $4$ times an odd prime power;
• $4$ and $8$.

Answer 2

This is a question about the structure theory of finite abelian groups. You are asking for the minimum size of generators for the multiplicative group $\Bbb{Z}_n^*$ of residue classes coprime to $n$. As is often the case the Chinese remainder theorem is your friend. If $$ n=\prod_{j=1}^kp_j^{a_j}\qquad(*) $$ is the prime factorization of $n$, then CRT tells us that $$ \Bbb{Z}_n^*\cong\prod_j\Bbb{Z}_{p_j^{a_j}}. $$ Furthermore, it is well known that for $n\ge2$ $$ \Bbb{Z}_{2^n}^*\cong C_2\times C_{2^{n-2}} $$ with the former factor generated by $-1$ and the latter by $5$. For all the odd primes $p$, the situation is simpler, and $$ \Bbb{Z}_{p^n}^*\cong C_{p^{n-1}(p-1)} $$ is cyclic (in other words, there exists a primitive root modulo a power of an odd prime). Putting these together gives us a way of writing $\Bbb{Z}_n^*$ as a direct product of cyclic groups.

To answer the question about the minimal number of generators we need an elementary result from the structure theory of finite abelian groups. Namely, that a finite abelian group $G$ can be written as a direct product of cyclic groups $$ G=C_{d_1}\times C_{d_2}\times \cdots\times C_{d_k}\qquad(**) $$ in such a way that $d_i\mid d_{i+1}$ for all $i=1,2,\ldots,k-1$. The numbers $d_i$ are known as invariant factors of $G$ and, as the name suggests, they are uniquely determined by the group $G$.

Without loss of generality we can assume that $d_1>1$. Given this, it follows that

The minimum number of generators for $G$ is equal to $k$.

A proof follows from $(**)$ easily. Obviously a set of generators of the factors, one for each, generates all of $G$. So $k$ generators suffices. OTOH, if $p$ is a prime divisor of $d_1$, then $G$ has $C_p^k$ as a quotient group. That is, a $k$-dimensional vector space over the field $\Bbb{Z}_p$. That group requires a minimum of $k$ generators (=basis vectors) by linear algebra. Hence, so does $G$.

---

How does this apply? The method for finding the invariant factors is algorithmic (and at least many instances have been covered on the site already). We can actually easily describe the number of invariant factors divisible by a fixed prime $q$ as follows.

Given $n$, the decomposition $(*)$, and a prime $q$, the number of invariant factors divisible by $q$, call it $\ell(n,q)$ is gotten as the following sum: $$\ell(n,q)=\sum_j e(p_j,q),$$ where $$ e(p,q)= \begin{cases} 2,\ &\text{if $p=q=2$ and $8\mid n$},\\ 1,\ &\text{if $p=q=2$, $4\mid n$, but $8\nmid n$},\\ 1,\ &\text{if $p=q>2$, and $p^2\mid n$},\\ 1,\ &\text{if $p\neq q$, and $q\mid p-1$},\\ 0,\ &\text{in all the other cases.} \end{cases} $$ This follows by a study of the orders of all those cyclic factors. Again, $\Bbb{Z}_n^*$ will have a quotient group isomorphic to $C_q^{\ell(n,q)}$.

Then the final answer is:

The minimum number of generators of $\Bbb{Z}_n^*$ is the maximum of the numbers $\ell(n,q)$ with $q$ ranging over the primes.

---

Upon reading Greg Martin's fine answer I realized that $\ell(n,2)$ is always the maximum of the numbers $\ell(n,q)$. Therefore it suffices to calculate $\ell(n,2)$, and the answer is what Greg wrote.