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


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).

  • $\begingroup$ But how would I show that it is proper? What element wouldn't be in the set? $\endgroup$ – BridgeSkier Feb 11 '16 at 1:39
  • $\begingroup$ 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$. $\endgroup$ – André Nicolas Feb 11 '16 at 1:46

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.