Let $\overline{a} , \overline{b} \in \mathbb{Z}/n\mathbb{Z}$. Then $\langle \overline{a} \rangle \le \langle \overline{b} \rangle$ if and only if $(b,n) \mid (a,n)$, where $(x,y)$ denotes the greatest common divisor of $x$ and $y$.

This problem has plagued me for about a week or so now, and I have reached my limit. I have pages and pages of attempts. I could use some help.

  • $\begingroup$ As a pro-tip, when you have pages and pages of attempts, it's best to post some of them to help us see where you're stuck and your approximate math level so we can make better responses for you. $\endgroup$ – Adam Hughes Nov 21 '16 at 21:49

Recall the fourth isomorphism theorem, that says that the subgroups of a quotient are the same as subgroups of the original group which contain the kernel of the homomorphism.

So then we have the canonical projection:

$$\pi_n:\Bbb Z\to \Bbb Z/n\Bbb Z$$

We know the kernel is exactly $\langle n\rangle$ and that all subgroups containing the kernel are exactly $\langle d\rangle$ where $d|n$. The lift of a given $\bar{x}$ is just $\gcd(x,n)$ so we see

$$\langle\bar{a}\rangle\le\langle\bar{b}\rangle\iff\langle a,n\rangle\le\langle b,n\rangle$$

for the lifted subgroups which are the ones generated by $\gcd(a,n)$ and $\gcd(b,n)$. And this completes the proof.

Following the op's indication he has yet to learn the isomorphism theorems, here is an ad hoc approach:

Note that $\langle \bar a\rangle$ is made up of things in $\Bbb Z$ which are linear combinations of $n$ and $a$, since these generate the kernel. But then $\langle a,n \rangle = \{ax+ny : x,y\in\Bbb Z\}=\langle \gcd(a,n)\rangle$ because $\langle\bar a\rangle = \{\bar a\bar x : \bar x\in\Bbb Z/n\}$. But then as subsets of $\Bbb Z$ we note that $\langle x\rangle\subseteq\langle y\rangle$ iff all multiples of $x$ are also multiples of $y$, i.e. iff $y|x$. Hence $\langle\bar a\rangle \le \langle\bar b\rangle$ iff $\gcd(b,n) | \gcd(a,n)$.

| cite | improve this answer | |
  • $\begingroup$ I saw the your suggestion about posting some of my best attempts; I am sorry about that. Unfortunately, this problem, which is just a "footnote" in my textbook, comes before the isomorphism theorems. Is it possible to do this without reference to them? $\endgroup$ – user193319 Nov 21 '16 at 23:26
  • $\begingroup$ @user193319 it's more or less the same, you just reprove the containment statement in the middle in the language of $\Bbb Z$. The sets approach also uses the fact that $\{mx+ny: x,y\in\Bbb Z\}=\langle \gcd(m,n)\rangle$ which you should either already know of be able to easily prove. $\endgroup$ – Adam Hughes Nov 21 '16 at 23:38

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.