How can I know the number of solutions of the following congruence $x ^ {10} \equiv 1 \pmod {2016}$?

Question

How can I know the number of solutions of the following congruence $x ^ {10} \equiv 1 \pmod {2016}$?

My professor quick answer was:

$$\mathbb{Z_{2016}^*} \cong \mathbb{Z_{32}^*} \times \mathbb{Z_{9}^*} \times \mathbb{Z_{7}^*} \cong (C_{8} \times C_{2}) \times C_{6} \times C_{6} \cong (C_{8} \times C_{2}) \times (C_{2} \times C_{3}) \times (C_{2} \times C_{3}) $$

Where $\mathbb{Z^*}$ is the group of units and $C_{n}$ is the cyclic group of order n.

My question related to this part is why he did not use $C_{16}$ or $C_{4} \times C_{4}$ instead of $C_{8} \times C_{2}$, could anyone explain this for me please?

Then My professor added: "then the number of solutions of the given congruence is $|C_{2} \times C_{2} \times C_{2} \times 1 \times C_{2} \times 1 | = 2^4 =16$"

I understand part of this part, he neglected the $C_{3}$ group as it will not contain elements of order 2 (which I do not know why? could anyone explain this for me please?). Also, he took one $C_{2}$ group of $C_{8}$ (which I do not understand why? as far as I know $\mathbb{Z_{mn}} \cong \mathbb{Z_{n}} \times \mathbb{Z_{m}}$ iff gcd(m,n) = 1, and gcd(4,2) $\neq$ 1)

Could anyone elaborate these parts for me please?

Note: I have asked my professor but he answered these question in a very fast way so that I could not follow him.

The steps my professor do before answering this number of solutions question are:

He used the Euler-Phi function to find $\phi (2016) = 576 $ then he used Euler's theorem, then he noticed that $gcd(10, 576) = 2$, so he ended up with the congruence $$x ^ {2} \equiv 1 \pmod {2016}$$, and he said hence the order of of $x$ is either 1 or 2, but the identity element is the only element of order 1, so our $x$ has order 2, this is why we were searching for $C_{2}$ in the above isomorphisms.

But my question is: does not $C_{16}, C_{8}, C_{4}$ or $C_{3}$ contains elements of order 2?

Thanks!

Answer 1

Let's look at the multiplicative units modulo $32$, which we can write as $\pm 1, \pm 3, \pm 5, \pm 7, \pm 9, \pm 11, \pm 13, \pm 15$.

There are $16$ units and we immediately have $1$ of order $1$ and $-1$ of order $2$. The others will have orders which divide the order of the group and hence have order a power of $2$.

The respective squares are $1, 9, -7, -15, -15, -7, 9, 1$

There are thus four elements satisfying $x^2=1$ namely $\pm 1, \pm 15$ (And the group cannot be cyclic) whence $\pm 15$ also have order $2$.

The fourth powers are $1, -15, -15, 1, 1, -15, -15, 1$ and there are eight elements which satisfy $x^4=1$, hence four elements of order $4$.

The remaining eight elements have order $8$. Pick one and it generates a cyclic subgroup of order $8$. The whole group is the direct product of this $C_8$ with the subgroup of order $2$ generated by one of the elements of order $2$ (depending which is in the $C_8$ you have chosen).

So your professor is invoking a theorem on the structure of the multiplicative group of units of $\mathbb Z_{2^r}$ which is $C_{2^{r-2}} \times C_2$

That disposes of the factor $32$ - the group is $C_8\times C_2$ and not $C_4\times C_4$ because that is what it is.

---

The other factors do represent cyclic groups, but there is an isomorphism between $C_2\times C_3$ and $C_6$ which means that your professor can extract a factor $C_2$ - he is interested in the elements of order $2$ (or $5$ or $10$ - but there are none of these, because the order of the original group is not divisible by $5$).

---

An element satisfying $x^2=1$ must have order $1$ or $2$ in all its components.

---

Answer 2

A starting point for problems like this is Lagrange's theorem (in group theory), which tells us the order of any subgroup of a finite group divides the order of the group itself, and hence the order of any element (the order of the cyclic subgroup it generates) divides the order of a finite group containing it. A priori if we only knew the group was abelian of order $2016$, then indeed we would not know whether it had a factor of $C_9$ or merely $C_3$.

But here we know something more: our group $\mathbb Z/ 2016\mathbb Z$ is cyclic of order $2016$. Since the generator of this cyclic (abelian) group is $1$, it has multiples that have order any divisor of $2016$ that you like. Because of this the Fundamental Thm. of Abelian Groups is here satisfied by representation:

$$ \mathbb Z/ 2016\mathbb Z \cong \mathbb Z/32\mathbb Z \times \mathbb Z/ 9\mathbb Z \times \mathbb Z/7\mathbb Z $$

and the ring structure on $\mathbb Z_{2016}$ has to agree (because here the abelian group with its natural $\mathbb Z$-module structure has a consistent "multiplication" operation).

So when we ask about the multiplicative subgroups, elements that are coprime to $2016$ are precisely those coprime to its prime power factors, $32, 9$ and $7$. Thus one might show by the Chinese Remainder Theorem:

$$ \mathbb Z_{2016}^* \cong \mathbb Z_{32}^* \times \mathbb Z_9^* \times \mathbb Z_7^* $$

I.e. whatever coprime residues you choose with respect to $32,9,7$ respectively can be achieved by a choice of residue with respect to $2016$ (and that element will necessarily be coprime to $2016$). Conversely any element coprime to $2016$ will give coprime residues with respect to $32,9,7$ also.

---

Circling back to the problem posed in the title of the Question, how can this information help us to find "the number of solutions" to $x^{10}\equiv 1 \bmod 2016$ ?

This is a polynomial equation, and what it requires is that a group element have an order that divides $10$. So for example $x=1$ (order $1$) and $x=-1$ (order $2$) are solutions found "by inspection". Keeping in mind that the order of an element must divide the order of the group motivates us to examine the structure of a multiplicative group of integers modulo n and how large such a group is.

Because the equation is polynomial, the structure of:

$$ \mathbb Z_{2016}^* \cong \mathbb Z_{32}^* \times \mathbb Z_9^* \times \mathbb Z_7^* $$

leads us to observe that an element of $\mathbb Z_{2016}^*$ is essentially a triple of "coordinates", one from each respective direct summand. The size of the entire group is the product of the sizes of these group factors, and the general formula $|\mathbb Z_n^*| = \phi(n)$ based on Euler's phi-function becomes especially easy to compute when the factors of prime power orders are given:

$$ \phi(32) = 16, \phi(9) = 6, \phi(7) = 6 $$

A solution $x\in \mathbb Z_{2016}^*$ would therefore correspond to a triple $(a,b,c)$ of solutions to the same polynomial equation for the respective group factors. Note that none of these subgroup orders are divisible by $5$, so really all we are looking for are elements in these factors of order $1$ or $2$.

An element of order $1$ is simply the (multiplicative) identity element in each subgroup. The interesting kinds of solutions will have order $2$.

Now it has been known since Gauss which of these multiplicative groups modulo integer $n$ are cyclic, namely $n = 1,2,4,p^k,$ and $2p^k$ for prime $p$ and positive integer power $k$. Thus both $\mathbb Z_9^*$ and $\mathbb Z_7^*$ are cyclic groups of order six. Finding a generator for each of these (an element of multiplicative order six) will provide the only elements of order $1$ and $2$ (by raising the generator to the sixth and third power respectively). But we already found them by inspection, $\pm 1$ in the respective modulo groups.

So the first "coordinate" in $\mathbb Z_{32}^*$ will be the most interesting to solve. This is an abelian group of order $16$, but not a cyclic group. Instead one finds, as explained in the Wikipedia article linked above, that in general the powers of two give a product of two cyclic groups:

$$ \mathbb Z_{2^{k+1}}^* \cong C_2 \times C_{2^{k-1}} $$

In our specific case $\mathbb Z_{32}^* \cong C_2 \times C_8$.

If we are only interested (as the title asked) in "the number of solutions", then it suffices to say $\mathbb Z_{32}^*$ has four elements of order at most $2$. Putting all of the information together, we have four choice for the first "coordinate" and two choices each for the second and third. Thus $x^{10}\equiv 1 \bmod 2016$ will have $4\cdot 2\cdot 2 = 16$ distinct solutions.

Although we omit the explicit determination of these, the motivated Reader will be heartened to know that the work in $\mathbb Z_{32}^*$ is limited finding four solutions, out of which the two $\pm 1$ are known already.