More on coprime integers

**Louise** · February 1st 2009, 07:06 AM

Let n and m be coprime positive integers. Show that if n divides a and m divides a then nm divides a. Deduce that nm is the least common multiple of n and m.

I have shown the first part by expressing a as a product of distinct prime numbers but not the deduction.

I'm also having trouble with the following;

Suppose that n and m are arbitrary positive integers. Show that if n divides a and m divides a then nm/(n,m) divides a. Deduce that nm/(n,m) is the least common multiple of n and m.

Thank-you for your help.

**star_tenshi** · February 1st 2009, 04:47 PM

For the first part, I got this from Niven 5th edition:

There exist integers $x_{0}, y_{0}, x_{1}, y_{1}$ such that $1 = mx_{0} + ay_{0} = nx_{1} + ay_{1}$

Thus,
$mx_{0} = 1 - ay_{0}$
$nx_{1} = 1 - ay_{1}$ and gives....
$(mx_{0})(nx_{1}) = (1 - ay_{0})(1 - ay_{1}) = 1 - a(y_{0} + y_{1} - ay_{0}y_{1})$

Rearranging, we get:
$1 = mnx_{0}x_{1} + a(y_{0} + y_{1} - ay_{0}y_{1})$
which is in the form $1 = mn (some integer) + a (some integer)$
and in the form of the gcd.

Thus $(nm,a) = 1$

**star_tenshi** · February 1st 2009, 05:30 PM

For the second part, this may help:

Theorem: $gcd(m,n) \cdot lcm(m,n) = |mn|$

Proof:
$gcd(m,n) = gcd(|m|,|n|)$
and $lcm(m,n) = lcm(|m|,|n|)$ thus we can assume $m,n > 0$

Let $gcd(m,n) = d$
Thus $d|a$ and $d|b$ ...which gives... $m = dr$ and $n=ds$ for some integers $r,s$

Let $l=\frac{mn}{d}$
then claim $l = lcm(m,n)$
$m = dr \Rightarrow l = rn \Rightarrow n|l$
$n = ds \Rightarrow l = sm \Rightarrow m|l$
here we have shown that $l$ is a common multiple of $m$ and $n$ .

Let $c$ be some common multiple of $m$ and $n$ .
$\Rightarrow \exists u,v$ integers such that $c = mu$ and $c = nv$

Since $d = gcd(m,n)$ then $d = mx + ny$
$\frac{c}{l} = \frac{cd}{mn} = \frac{c(mx+ny)}{mn} = \frac{cmx}{mn} + \frac{cny}{mn} = \frac{cx}{n} + \frac{cy}{m}$ but $c = mu = nv$

Thus $\frac{c}{l} = vx + uy$ which is an integer.

This proves that any generic common multiple $c$ is divisible by $l$ and we can conclude that $l$ is the $lcm(m,n)$

Thus $l = \frac{mn}{d} \Rightarrow lcm(m,n) = \frac{mn}{gcd(m,n)}$

Thread: More on coprime integers

LinkBack

Thread Tools

Display

More on coprime integers

Similar Math Help Forum Discussions

comaximal(coprime)

Coprime Proof

coprime

Coprime Theorem II

Coprime

Search Tags