1
$\begingroup$

Let $a,b\in \mathbb{N}$ and $m=\operatorname{lcm}(a,b)$. Prove that $\gcd(\frac{m}{a},\frac{m}{b})=1$.

Any suggestion how to prove I would appreciate. I have try to it directly but I don't get anything. Probably I'm doing some dumb mistake.

$\endgroup$
3
$\begingroup$

Let $m = \operatorname{lcm}(a,b)$, then $\gcd(a,b)= \frac{ab}m$.

We know that there exist integers $x,y$ such that $\frac{ab}{m} = ax + by$. Now, multiplying by $m$, we get $ab = max+mby$. Dividing by $ab$, we get $1 = x\left(\frac{m}{b}\right) + y\left(\frac{m}{a}\right)$. Hence, there exist intgers $x,y$ such that the above happens. By Bezout's theorem, it follows that $\frac mb, \frac ma$ are co-prime.

$\endgroup$
  • 2
    $\begingroup$ You don't really need Bézout here, just the fact that $1$ is not divisible by any larger integer. $\endgroup$ – Erick Wong Feb 3 '17 at 5:15
  • $\begingroup$ @ErickWong Oh, Bezout looks nice. That's it. I knew there was the way you suggested, but then this answer is a little more "romantic" to me, it's a different approach. $\endgroup$ – астон вілла олоф мэллбэрг Feb 3 '17 at 5:16
  • 1
    $\begingroup$ @ErickWong Implicit in the above is a duality based on cofactors of $ab$. I bring this innate structure to the fore in my answer. $\endgroup$ – Bill Dubuque Jul 1 '17 at 20:01
2
$\begingroup$

Let's set $d=\gcd(\frac{m}{a}, \frac{m}{b})$, then $d\mid \frac{m}{a}$ and $d\mid \frac{m}{b}$, which lead us to $a\mid \frac{m}{d}$ and $b\mid \frac{m}{d}$. Then by the definition of $\text{lcm}$ we deduce that $m\mid \frac{m}{d}$, so $d\mid \frac{m}{m}=1$ and hence $d=1$.

$\endgroup$
  • $\begingroup$ See my answer for an explanation of the innate duality lying behind this proof. $\endgroup$ – Bill Dubuque Jun 30 '17 at 22:38
2
$\begingroup$

The result is the special case $\, m = {\rm lcm}(a,b),\,$ in the following Theorem, whose proof is a completely mechanical application of $\,\rm\color{#c00}{cofactor\ duality}\,$ and $\,\rm\color{#0a0}{universal}\,$ properties of gcd, lcm

Theorem $\ \ \ \displaystyle \overbrace{ \gcd\left(\frac{m}a,\frac{m}b\right)^{\phantom{|}}}^{\Large \gcd\,(a',\ b')\,}\! =\, \overbrace{\frac{m}{{\rm lcm}(a,b)}^{\phantom{|}}}^{\Large {\rm lcm}(a,b)'}\, $ for $\,m\,$ any common multiple of $a,b,\,$ since

$\displaystyle d\mid \gcd\!\left (\frac{m}a,\,\frac{m}b\right) \!\!\color{#0a0}\iff\! d\,\ \Bigl\vert\ \frac{m}a,\,\frac{m}b \!\color{#c00}\iff\! a,b\ \Bigl\vert\ \frac{m}d \!\color{#0a0}\iff\! {\rm lcm}(a,b)\ \Bigl\vert\ \frac{m}d \!\color{#c00}\iff\!d\ \Bigl\vert\ {\frac{m}{{\rm lcm}(a,b)}}$


i.e. $\ d\mid\gcd(a',b')\!\iff d\,\mid a',\ b'\color{#c00}\iff\, a,b\mid d' \iff {\rm lcm}(a,b)\mid\, d'\!\color{#c00}\iff d\mid {\rm lcm}(a,b)' $

i.e. $\,\ \bbox[6px,border:1px solid red]{\gcd(a',b') = {\rm lcm}(a,b)' } \ $ where $\ n':= m/n\,$ denotes the cofactor of any divisor $n$ of $m$

The following cofactor duality is the source of the prime-flipped divisibilities in the $\rm\color{#c00}{red}$ arrows

$$ x\,\mid\, y\:\color{#c00}\iff\: y'\mid x'\ \ \ {\rm by}\ \ \ \dfrac{y}x = \dfrac{x'}{y'} \ \ \ {\rm by}\ \ \ yy' = m = xx' $$

This duality between gcd and lcm is a divisibility analog of DeMorgan's Laws (this will be made more precise if one studies lattice theory, e.g. see Birkhoff's books).


Corollary $\ \displaystyle \ \gcd(b,\,a)\, =\, \frac{ab}{{\rm lcm}(a,b)}\,\ $ by $\ m = ab\ $ in the Theorem.

If the prior is already known (e.g. here) then it can be applied to derive the sought result:

$\quad ab\, =\!\!\!\!\! \overbrace{m}^{\large {\rm lcm}(a,b)}\!\!\!\!\!\!\gcd(a,b)\, =\, \gcd(ma,mb)\, =\, ab\gcd(\frac{m}b,\frac{m}a)\ $ by the GCD Distributive Law

Thus canceling $\,ab\,$ yields $\, 1 = \gcd\left(\frac{m}b,\frac{m}a\right).$

$\endgroup$
  • $\begingroup$ Very belated, but thank you for this answer : it is illustrative. I think by lattice here, you refer to a poset with glb and lub existing for ever subposet, right? In that case, probably De Morgan holds. For positive divisors of a natural number ordered by division, this property holds with gcd,lcm serving as glb,lub, so the result follows. I like this result. $\endgroup$ – астон вілла олоф мэллбэрг Oct 5 '18 at 4:11
0
$\begingroup$

Let $\operatorname{hcf}(a,b)=d$. Then there exists $p,q$ such that $a=pd$, $b=qd$, such that $\operatorname{hcf}(p,q)=1$. Therefore, $\operatorname{lcm}(a,b)=pqd=m$. Also, $\frac{m}{a} =q$ and $\frac{m}{b} =p$, and the result follows.

$\endgroup$

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.