$a\times na = LCM(a, b) = b\times nb$. Show that $GCD(na, nb) = 1$.

Question

I have this question that I have been trying to get my head around for the past couple of hours and I am not getting anywhere with it...

Let $a,b \in \mathbb{N}$. Further, let $n_a, n_b \in \mathbb{N}$, so that $a \times n_a = LCM(a, b) = b \times n_b$.

Show that $GCD(n_a, n_b) = 1$.

I know that if the GCD was $1$, then that means that the numbers are relatively prime. But I was unable to get much further with the idea. Anyhelp would be appreciated.

Thanks!

Answer 1

Let $n_a = c\times m_a$, $n_b=c\times m_b$, $c = GCD(n_a, n_b)$

$$a\times m_a = \frac{a\times n_a}{c} = \frac{b\times n_b}{c} = b\times m_b$$

So,

$$LCM(a,b) | a\times m_a \implies a\times c\times m_a| a\times m_a \implies c = 1$$

Answer 2

It's straightforward if you use the prime factorization definition of least common multiple.

Write $a$ as a product of prime numbers $$a = \prod\limits_p p^{\textrm{ord}_p a}$$

where $p$ runs through all the prime numbers, and $\textrm{ord}_p a$ is the multiplicity with which $p$ occurs as a divisor of $a$. Of course this is a finite product, which is to say that $\textrm{ord}_p a = 0$ for all but finitely many primes $p$. Do the same for $b$. Then the least common multiple of $a$ and $b$ is

$$\prod\limits_p p^{\textrm{Max} \{ \textrm{ord}_p a, \textrm{ord}_p b\} }$$

For example if $a = 60 = 2^2 \cdot 3 \cdot 5$, and $b = 315 = 3^2 \cdot 5 \cdot 7$, then the least common multiple of $a$ and $b$ is

$$2^2 \cdot 3^2 \cdot 5 \cdot 7 = 1260$$

Now for any prime $p$, it is easy to see that $\textrm{ord}_p xy = \textrm{ord}_p x + \textrm{ord}_p y$ for any integers $x, y$. And so $$a n_a = \prod\limits_p p^{\textrm{ord}_p a + \textrm{ord}_p n_a}; b n_b = \prod\limits_p p^{\textrm{ord}_p b + \textrm{ord}_p n_b}$$

To say that the least commmon multiple of $an_a$ and $bn_b$ is the same as that of $a$ and $b$, is the same thing as saying that for every prime number $p$,

$$\textrm{Max} \{ \textrm{ord}_p a, \textrm{ord}_p b\} = \textrm{Max} \{ \textrm{ord}_p a + \textrm{ord}_p n_a, \textrm{ord}_p b + \textrm{ord}_p n_b \}$$

In general if you have nonnegative integers $x, y, z, w$, and the maximum of $x, z$ is the same as the maximum of $x+y,z+w$, the only way this can happen is if one of the integers $y$ or $w$ is zero.

Thus for every prime number $p$, one of the numbers $\textrm{ord}_p n_a$ or $\textrm{ord}_p n_b$ is zero. This is the same as saying that $n_a$ and $n_b$ are never divisible by the same prime number, which is the same as saying that the greatest common divisor of $n_a, n_b$ is $1$.

Answer 3

$d\mid n_a,n_b\Rightarrow\, \underbrace{a\Big({\large\frac{n_a}d}\Big) =\,{\large\frac{{\rm lcm}(a,b)}{d}}\, =\, b\Big({\large\frac{n_b}d}\Big)}_{\large \text{cancel $d$ from original equation}}$ $\Rightarrow$ $\,a,b\mid {\rm lcm}(a,b)/d,\,$ contra leastness of lcm if $d>1$