# Thread: Groups (Z mod p)

1. ## Groups (Z mod p)

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

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

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

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

Please help

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

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

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

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