Prove that if $\gcd(m,n)=d$, then $\frac{n}{d}$ is the minimum $x$ such that $mx$ is divisible by $n$

Question

I am looking for the proof in the title because I am trying to prove that if $G$ is a cyclic group of order n with generator $a$, then the subgroup generated by $a^m$ has order $n/(m,n)$. I already understand that the order of the group is the same as the order of the generator, but I fail to grasp how the order can be related to gcd.

I know there is a related question in : Let $G$ be a cyclic group of order $n$. Prove that every subgroup $H$ of $G$ is of the form $<a^m>$ where $m$ is a divisor of $n$.. But I am interested in the evaluation of the order of the subgroup.

Answer 1

Since $\gcd(m, n) = d$, from Bézout's identity, $\exists\, p, q$ such that $p m + qn = d$.

Suppose $\exists \,x >0$ such that $n|mx$, then $n|dx$, which means $x \geq \frac{n}{d}$. We can easily verify that $n|dx$ when $x = n/d$, thus it's the minimum.

Answer 2

Isn't that implicit in the definition of $\gcd$ ? if $mn= d*x$ and $d$ is maximum, then $x$ is minimum.

Answer 3

We have that $n|mx$ and $m|mx$ which implies $l=lcm(m,n)|mx\Rightarrow\ mn|mdx\Rightarrow\ n|dx\Rightarrow\ x\ge\frac nd$

Answer 4

If you are using this in an exercise in Abstract Algebra we can accept this as an established arithmetic result that everyone accepts.

The proof would be $n = n'd$ and $m = m'd$ for some integers $n',m'$. If $n'$ and $m'$ had any factors $g$ in common then $gd$ would be a common divisor of $n$ and $m$ but $d$ is the greatest common divisor of $m$ and $n$ so $m'$ and $n'$ are relatively prime.

then if $n$ divides $mx$ that would be the same as $n'$ divides $m'x$ and and as $n'$ and $m'$ have no factors in common that would mean $n'$ divides $x$. Clearly the smallest $x$ that is divisible by $n'$ is $x = n'= \frac nd$.

....

or, arghh, as AnotherJohnDoe points out $n$ dividing $mx$ means $mx$ is common multiple of $n,m$ and the least such number would be the least common multiple ... which is $\frac {mn}d$. In the back of my mind I knew it was that simple but somehow the exact words didn't come out of my typing fingers.

Answer 5

Note $\ n\mid mx,nx\iff n\mid (mx,nx)\!=\! \overbrace{(m,n)}^{\large d}x \iff n/d\mid x,\, $ using the GCD Distributive Law

This proof is more general than proofs using Bezout since it works in domains like $\,\Bbb Z[x],\, \Bbb F[x,y]$ where gcds needn't have Bezout linear form, e.g. $(2,x) = 1 = (x,y)$