# Proof about least nonnegative residue modulo m when m has no primitive roots

What is the least nonnegative residue modulo 𝑚 of the product of all positive integers not exceeding 𝑚 and relatively prime to 𝑚, if no primitive root modulo 𝑚 exists? Prove your assertion.

I know that if m has a primitive root, then it is equal to 1, 2, 4, p^n, or 2p^n where n is a positive integer and p is an odd prime. I tried thinking about cases where this is not true and solving x = a (mod m) for a when x is the product of all positive integers not exceeding m and relatively prime to m. Beyond this I am lost.

$$\mathbb{Z}_m^*$$ is the set of elements $$x\in\mathbb{Z}_m=\dfrac{\mathbb{Z}}{m\mathbb{Z}}$$ such that $$x$$ has a multiplicative inverse.

The question supposes that $$\mathbb{Z}_m^*$$ is not a cyclic group.

$$\\$$

$$\mathbb{Z}_m^*$$ is nevertheless a finite abelian group.

Every finite abelian group is isomorphic to $$\mathbb{Z}_{q_1}\oplus\ldots\oplus\mathbb{Z}_{q_k}$$, where the $$q_i$$ are all prime powers. This decomposition is unique up to an ordering of $$q_i$$. This is the fundamental theorem of finite abelian groups.

I am going to call this a fundamental decomposition.

$$\\$$

We want to evaluate $$\displaystyle\prod_{y\in\mathbb{Z}_m^*}y$$, right?

Re-expressing $$\mathbb{Z}_m^*$$ as the above direct sum,

we simply need to evaluate $$S=\displaystyle\sum_{r\in\mathbb{Z}_{q_1}\oplus\ldots\oplus\mathbb{Z}_{q_k}}r=(s_1,\ldots,s_k)$$

where $$s_i\in\mathbb{Z}_{q_i}$$ and $$s_i=\displaystyle\left(\prod_{j\neq i}q_j\right)\times\sum_{t\in\mathbb{Z}_{q_i}}t$$.

Notice that for an odd prime power $$q$$, we have $$\displaystyle\sum_{a\in\mathbb{Z}_q}a=0$$. This means that if $$q_j$$ is an odd prime power for a given $$j$$, then $$s_j=0$$.

Instead if $$q$$ is an even prime power, i.e. if $$q=2^h$$, then $$\displaystyle\sum_{a\in\mathbb{Z}_q}a=2^{h-1}$$. Observe that $$2\times2^{h-1}=0$$ in $$\mathbb{Z}_q$$. Therefore, if you are given $$i\neq j$$ such that $$q_i$$ and $$q_j$$ are both even prime powers, then $$s_i=0$$ and $$s_j=0$$.

$$\\$$

Therefore, we would like to prove that the condition in the question, namely that $$\mathbb{Z}_m^*$$ is not a cyclic group,

implies that in the fundamental decomposition $$\mathbb{Z}_m^*\cong\mathbb{Z}_{q_1}\oplus\ldots\oplus\mathbb{Z}_{q_k}$$,

there exist $$j_1\neq j_2$$ such that $$q_{j_1}=2^{h_1}$$ and $$q_{j_2}=2^{h_2}$$.

$$\\$$

Let $$m=p_1^{a_1}\ldots p_n^{a_n}$$, where the $$p_i$$ are distinct primes.

Due to the Chinese Remainder Theorem,

$$\mathbb{Z}_m^*\cong (\mathbb{Z}_{p_1^{a_1}})^*\oplus\ldots\oplus(\mathbb{Z}_{p_n^{a_n}})^*$$.

Recall that the size of $$(\mathbb{Z}_{p^a})^*$$ is $$\phi(p^a)=p^{a-1}(p-1)$$, which is an even number except when $$p^a=2$$.

Furthermore, if $$G=H_1\oplus\ldots\oplus H_n$$, the fundamental decomposition of $$G$$ is equal to the direct sum of the fundamental decomposition of each $$H_i$$.

Also, if $$p$$ divides the size of $$H$$, then one of the terms in the fundamental decomposition of $$H$$ will be $$\mathbb{Z}_{p^a}$$ for some $$a\geq 1$$.

$$\\$$

Therefore, if you can find $$i\neq j$$ such that $$p_i^{a_i}\neq 2$$ and $$p_j^{a_j}\neq 2$$, then the fundamental decomposition of $$(\mathbb{Z}_{p_i^{a_i}})^*$$ will have a term of the form $$\mathbb{Z}_{q}$$, where $$q$$ is some power of $$2$$. You can say the same for $$(\mathbb{Z}_{p_j^{a_j}})^*$$.

This will be enough to show that $$S=(0,\ldots,0)$$.

The only cases left to check are:

• $$m=p^a$$ or $$m=2p^a$$, where $$p$$ is an odd prime and $$a\geq 1$$. But as you have stated in your question, you already know that there is a primitive root $$\text{mod}(m)$$ in these cases, which you can therefore ignore.
• $$m=2$$ and $$m=4$$, which you can also ignore.
• $$m=2^a$$ for $$a>2$$. In this case, refer to this Wikipedia entry to see why $$\mathbb{Z}_2\oplus\mathbb{Z}_2$$ is a subgroup of $$\mathbb{Z}_m^*$$. Notice that $$\mathbb{Z}_2\oplus\mathbb{Z}_2$$ is not a subgroup of $$\mathbb{Z}_{2^h}$$. Therefore, in the fundamental decomposition $$\mathbb{Z}_m^*\cong\mathbb{Z}_{q_1}\oplus\ldots\oplus\mathbb{Z}_{q_k}$$, there must be $$i\neq j$$ such that $$q_i$$ and $$q_j$$ are both powers of $$2$$.

$$\\$$

$$S=(0,\ldots,0)$$ corresponds to $$\displaystyle\prod_{y\in\mathbb{Z}_m^*}y=1$$,

because $$(0,\ldots,0)$$ is the identity element in $$\mathbb{Z}_{q_1}\oplus\ldots\oplus\mathbb{Z}_{q_k}$$,

and $$1$$ is the identity element in $$\mathbb{Z}_m^*$$.