Results 1 to 3 of 3

Math Help - More on coprime integers

  1. #1
    Junior Member
    Joined
    Oct 2008
    Posts
    38

    More on coprime integers

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member star_tenshi's Avatar
    Joined
    Jan 2009
    Posts
    32
    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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member star_tenshi's Avatar
    Joined
    Jan 2009
    Posts
    32
    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)}
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. comaximal(coprime)
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: March 15th 2010, 10:45 PM
  2. Coprime Proof
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: November 6th 2009, 08:47 AM
  3. coprime
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: September 13th 2009, 04:45 AM
  4. Coprime Theorem II
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: May 7th 2009, 06:27 PM
  5. Coprime
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 19th 2009, 10:32 AM

Search Tags


/mathhelpforum @mathhelpforum