# If $m=\operatorname{lcm}(a,b)$ then $\gcd(\frac{m}{a},\frac{m}{b})=1$

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.

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.

• You don't really need Bézout here, just the fact that $1$ is not divisible by any larger integer. – Erick Wong Feb 3 '17 at 5:15
• @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. – астон вілла олоф мэллбэрг Feb 3 '17 at 5:16
• @ErickWong Implicit in the above is a duality based on cofactors of $ab$. I bring this innate structure to the fore in my answer. – Bill Dubuque Jul 1 '17 at 20:01

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

• 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. – астон вілла олоф мэллбэрг Oct 5 '18 at 4:11

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

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

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.