# Structure of $Z/nZ$

I am trying to improve my understanding of structure of $Z/nZ$.

Facts I know so far:

1. $Z/nZ \cong \oplus_i Z/p_i^{k_i}$ - CRT(1).
2. $(Z/nZ)^* \cong \oplus_i (Z/p_i^{k_i})^*$. Not quite sure about my proof of this fact.(2)

Proof: We have $Z/nZ \cong \oplus_i Z/p_i^{k_i}$ and its isomorphism $\phi$ : $r \to (r_1, \dotso, r_m)$. Since homomorphism preserves inverses then $r^* \to (r_1^*, \dotso, r_n^*)$, where each $r_i$ must be a unit. Hence, every $r^*$ has its own unique (because of CRT isomorphism) inverse element.

3. $(Z/pZ)^*$ is cyclic of order $p - 1$. I don't understand this at all. Why its order is $p - 1$ and why it is cyclic?(3)

4. From previous statement we know $(Z/pZ)^*$ is cyclic: $(Z/p^{k}Z)^* = C_{p^{k} \ (p - 1)}$ , since $\phi(p^k) = p^{k}\cdot (p - 1)$.(4)

There is also a special case, when $p = 2$.

$(Z/2^{k}Z)^* = C_2 \times C_{2^{k - 2}}$ . It can be proven using the fact $ord\left<-1\right> = 2$, $ord\left<5\right> = 2^{k - 2}$ and $\left<5\right> \cap \left<-1\right> = {e}$.

From these facts I can conclude:

1. $(Z/pZ)^* \cong C_{p_2^{k_2} \ (p_2 - 1)} \times \dotso \times C_{p_n ^{k _ n} \ (p_n - 1)}\ \text{, if } (n \mod 2 = 0) \land (n \mod 4 \neq 0) \text{ note that in this case } C_{p_1 ^{k _ 1} \ (p_1 - 1)} = C_1 \text{ ,so the first term cancels out.}$.

2. $(Z/pZ)^* \cong C_2 \times C_{2^{k_1 - 2}} \times C_{p_2 ^{k _ 2} \ (p_2 - 1)} \times \dotso \times C_{p_n ^{k _ n} \ (p_n - 1)}$, since $(Z/2^{k}Z)^* = C_2 \times C_{2^{k - 2}}$, when $(n \mod 8 = 0)$

3. $(Z/pZ)^* \cong C_{p_1^{k_1} \ (p_1 - 1)} \times \dotso \times C_{p_n ^{k _ n} \ (p_n - 1)}$ , when $(n \mod 2 \neq 0) \ \lor ((n \mod 8 \neq 0) \land (n \mod 4 = 0))$, because of (2).

My questions are:

Can you please verify my conclusion?

Why $(Z/pZ)^*$ is cyclic of order $p - 1$?

How we can prove the fact: $(Z/pZ)^*$ is cyclic $\Rightarrow n = 2, 4, p^k, 2p^k$?

• By Euler criterion in number theory we have $a^{p-1}\equiv 1(mod p)$ – Mustafa Feb 5 '17 at 20:05
• Why there is no $m \in N\ m < p - 1$, such that $a^m = 1 \mod p$? – False Promise Feb 5 '17 at 20:23
• In general if $(a,m)=1$ then $a^{\phi(m)} \equiv 1(mod m)$ where $\phi(m)$ is Euler function – Mustafa Feb 5 '17 at 20:38
• Your statement in 4) is incorrect : We have that $\phi(p^k) = p^{k-1}(p-1)$. $\phi(n)$ is obviously smaller than $n$. – Marc Bogaerts Feb 6 '17 at 12:36
• @FalsePromise There are : if $p-1 = mn$ with $m < p-1$ and $b = a^n$ then $b^m = 1$.. In $C_2 \times C_2$ we have for each element $a^4$ but the group is not cyclic. – Marc Bogaerts Feb 6 '17 at 14:08

Why $(\Bbb Z/p\Bbb Z)^∗$ is cyclic of order $p−1$?

It should be clear that $p$ is prime. First of all note that $\Bbb Z/p\Bbb Z$ is a field, so every nonzero element is inverible. Let $k < p-1$ be the maximal order of the elements of $\Bbb Z/p\Bbb Z^*$. Then $\forall a \in \Bbb Z/p\Bbb Z^* : a^k = 1$. But this means that the polynomial $x^k-1$ of degree $k$ has $p-1 >k$ distinct roots, a contradiction, so $k = p-1$. So there is an element $a$ of order $p-1$. Such an element is called a primitive root.

How we can prove the fact: $\Bbb Z/p\Bbb Z$ is cyclic $\implies$ $n=2,4,p^k,2p^k$?

This question is rather ambiguous. I suppose that you ask for a proof that $\Bbb Z/n\Bbb Z$ is cyclic for $n=2,4,p^k,2p^k$ for an odd prime $p$. The cases 2 and 4 are easily proved by hand. In the case $n=p^k$ we have the following : If $a \in \Bbb Z_n^*$ (a simpler way of writing $\Bbb Z/n\Bbb Z^*$) is a primitive root of $\Bbb Z_p$ then either $a$ or $a+p$ is a primitive root of $\Bbb Z_{p^2}$, and if $a$ is a primitive root of $\Bbb Z_{p^2}$ then $a$ is a primitive root of $\Bbb Z_{p^k}$ for $k >2$. You can find these proofs here.

• It does /not/ imply that the two polynomials are identical (which I'm assuming means term-by-term equal). It means that the two polynomial have the same roots. But the larger one has all distinct roots by construction, contradiction. – Stella Biderman Feb 6 '17 at 13:56
• I agree, but that was implicitely implied: a polynomial of degree $< p-1$ having $p-1$ distinct roots. – Marc Bogaerts Feb 6 '17 at 14:01
• I think that the way it's phrased now is misleading, and that the term "identical" specifically should be removed. You could also say "... but this means that $x^k-1$ has $p-1>k$ distinct roots, contradiction." But that's not what I get out of reading what you've written. – Stella Biderman Feb 6 '17 at 14:18
• @StellaBiderman: I've edited it so there will be less confusion. – Marc Bogaerts Feb 6 '17 at 16:55
• @MarcBogaerts Actually the fact that the order of $(Z/nZ)^*$ is $p - 1$ clearly follows from the formula $\phi(p^k) = p^{k-1}(p-1) = p^k - p^{k - 1} < p^k$ (about your comment), since we define $\phi$ as the order of $(Z/nZ)^*$. In our case we got $\phi(p) = p^0\cdot (p - 1) = p - 1$. The fact that this is cyclic can be proven using the definition of exponent of a group (I'm not sure, but it seems to me that you're using this concept in your proof as $k$). And then, yes, I have to make a conclusion about number of roots etc. It all ends up that exponent of a group is its order. – False Promise Feb 7 '17 at 2:37