This site is currently being migrated at a new site. Please read the information below.

LaTeX

Unicode

Tuesday, February 23, 2016

Being a group implies that $n$ is prime

Prove that $(\mathbb{Z}_n^*, \otimes)$ is a group if and only if $n$ is prime.

Solution

$(\Rightarrow)$ Assume that $\mathbb{Z}_n^*=\{1,2,3,...n-1\}$ is a group. Suppose that $n$ is not a prime.

Then $n$ is composite, i.e $n=pq$ for $1<p,q<n-1$ . This implies that $pq \equiv0(\mod n)$ but $0$ is not in $\mathbb{Z}_n^*$. Contradiction, hence $n$ must be prime.

$(\Leftarrow)$ Suppose $n$ is a prime then  $\gcd(a,n)=1$ for every $a$ in $\mathbb{Z}_n^*$. Therefore, $ax=1-ny$, $x,y \in \mathbb{Z}_n^*$. So, $ax \equiv1(\mod n)$. That is every element of $\mathbb{Z}_n^*$  has an inverse. This concludes that $\mathbb{Z}_n^*$  must be a group since the identity is in $\mathbb{Z}_n^*$ and $\mathbb{Z}_n^*$ is associative.

No comments:

Post a Comment