# Groups (Z mod p)

• Jan 13th 2008, 07:32 AM
Jason Bourne
Groups (Z mod p)
(a) Show that if $p$ is prime, all non-zero elements of $\mathbb{Z}_{p}$ have a multiplicative inverse.

(b) Deduce that $\mathbb{Z}^*_{p}$, the set of non-zero elements of $\mathbb{Z}_{p}$, is a group under multiplication mod $p$.

(c) Show that if $n$ is not prime, then $\mathbb{Z}^*_{n}$ is not a multiplicative group.

(d) Is $\mathbb{Z}^*_{17}$ cyclic? (prime order :confused:)

• Jan 13th 2008, 09:19 AM
ThePerfectHacker
Quote:

Originally Posted by Jason Bourne
(a) Show that if $p$ is prime, all non-zero elements of $\mathbb{Z}_{p}$ have a multiplicative inverse.

Let $[x]_p \in \mathbb{Z}_p$ be a non-zero element (i.e. $[x]_p \not = \{ 0,\pm p,\pm 2p,...\}$). Now consider $\{ [x]_p,[2x]_p,...,[(p-1)x]_p\}$. None of these are equal to eachother, because otherwise $x i \equiv x j (\bmod p)$ since $\gcd (x,p)=1$ it means $i\equiv j (\bmod p)$ which is impossible since we are assuming that $i\not = j$. That means by pigeonhole principle that this set has to be a permutation of $\{ [1]_p,...,[p-1]_p\}$ in some order. And so, there exists $k$ such that $kx]_p = [1]_p$ thus $[k]_p[x]_p = [1]_p$ this means $[k]_p$ is an inverse for $[x]_p$.

Quote:

(b) Deduce that $\mathbb{Z}^*_{p}$, the set of non-zero elements of $\mathbb{Z}_{p}$, is a group under multiplication mod $p$.
I did the hard part in (a). You should be able to do this now.

Quote:

(c) Show that if $n$ is not prime, then $\mathbb{Z}^*_{n}$ is not a multiplicative group.
Just show there exists an element that does not have an inverse. Hint: if $n\geq 2$ is not prime then there exists $m\geq 2$ such that $\gcd (n,m)\not = 1$, and argue that no such $[x]_n$ can be found such that $[mx]_n = [1]_n$.

Quote:

(d) Is $\mathbb{Z}^*_{17}$ cyclic?
Yes.