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$?

  • $\begingroup$ By Euler criterion in number theory we have $a^{p-1}\equiv 1(mod p)$ $\endgroup$ – Mustafa Feb 5 '17 at 20:05
  • $\begingroup$ Why there is no $m \in N\ m < p - 1$, such that $a^m = 1 \mod p$? $\endgroup$ – False Promise Feb 5 '17 at 20:23
  • $\begingroup$ In general if $(a,m)=1$ then $a^{\phi(m)} \equiv 1(mod m) $ where $\phi(m) $ is Euler function $\endgroup$ – Mustafa Feb 5 '17 at 20:38
  • $\begingroup$ Your statement in 4) is incorrect : We have that $\phi(p^k) = p^{k-1}(p-1)$. $\phi(n)$ is obviously smaller than $n$. $\endgroup$ – Marc Bogaerts Feb 6 '17 at 12:36
  • $\begingroup$ @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. $\endgroup$ – 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.

| cite | improve this answer | |
  • $\begingroup$ 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. $\endgroup$ – Stella Biderman Feb 6 '17 at 13:56
  • $\begingroup$ I agree, but that was implicitely implied: a polynomial of degree $< p-1$ having $p-1$ distinct roots. $\endgroup$ – Marc Bogaerts Feb 6 '17 at 14:01
  • $\begingroup$ 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. $\endgroup$ – Stella Biderman Feb 6 '17 at 14:18
  • $\begingroup$ @StellaBiderman: I've edited it so there will be less confusion. $\endgroup$ – Marc Bogaerts Feb 6 '17 at 16:55
  • $\begingroup$ @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. $\endgroup$ – False Promise Feb 7 '17 at 2:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.