# Let $n \geq 2$ be an integer, and consider the group $Z_n:=(\{0,1,. . .,n-1\}, +_n)$. Let $k \in Z_n$ \ $\{0\}$.

Let $n \geq 2$ be an integer, and consider the group $Z_n:=(\{0,1,. . .,n-1\}, +_n)$. Let $k \in Z_n$ \ $\{0\}$. Show that the following statements are equivalent:

(a) $\gcd(n,k)=1$,

(b) the only subgroup of $Z_n$ that contains $k$ is $Z_n$ itself.

I am needing help understanding how to prove (b) implies (a). Any assistance would help. I

## 1 Answer

Outline: Suppose to the contrary that $d\gt 0$ divides both $k$ and $n$. Let $S$ be set of all numbers in the set $\{0,1,\dots,n-1\}$ that are, in the ordinary sense, divisible by $d$. Show that $S$ is a proper subgroup of $G$.

Parenthetically, I think that showing that (a) implies (b) is harder than showing that (b) implies (a).

• But how would I show that it is proper? What element wouldn't be in the set? – BridgeSkier Feb 11 '16 at 1:39
• If $d\gt 1$, then in particular $1$ is not divisible by $d$, so $1$ is not in $S$. I hope you have found the subgroup proof easy. All we need to show is that the sum of two elements of $S$ is in $S$, and that the "inverse" $n-s$ of an element of $S$ is in $S$. – André Nicolas Feb 11 '16 at 1:46