1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Abstract/Modern Algebra - Relatively Prime

  1. Feb 6, 2008 #1
    1. The problem statement, all variables and given/known data
    Note: gcd(a,b) = the greatest common divisor of integers a and b (not both 0)

    suppose that (a,b)=1 and (a,c)=1
    that is, a and b are relatively prime, and a and c are relatively prime

    Is the following statement true? if so prove it

    (bc,a)=1

    I computed a few examples, and i claim that it is true



    2. Relevant equations

    theorem: linear combination of gcd

    if d = gcd(a,b)

    then there exists integers u and v such that

    d = au + bv

    corollary:

    (a,b)=1 if and only if 1 = au +bv


    3. The attempt at a solution
    From the corollary stated above, i claimed that we must show that

    1 = (bc)u + (a)v

    thus we must find integers u and v that satisfy the statement above

    since (a,b) = 1 and (a,c) = 1, I used that corollary again,

    1 = ax + by and 1 = af + cg
    for some integers x,y,f, and g

    and i am stuck at this point. I have no idea what i can do with these statements

    I'm not sure if my approach is correct. But in the textbook, and in my class notes there are no examples showing how we can prove two integers are relatively prime. So i assumed this is how we approach the problem

    the only other thing we have learned so far, is the divisibility algorithm, and division

    any hints, guidance, would be appreciated. thanks

    edit: possible solution

    i see, that's the final step missing

    i said since
    (a,b) = 1 --> 1 = ax + by
    (a,c) = 1 --> 1 = af + cg
    By Theorem, x,y,f, and g exist

    1 = 1.1 = (ax+by)(af+cg) = a^2xf + axcg + aabyf + bycg
    = a(axf + xcg + byf) + bc(yg)
    therefore let

    u = axf + xcg + byf
    and
    v = yg

    and since, all the "letters" used exist and are integers, they satisfy the domain, and the proposition

    is that correct? even though "u" is messy, it doesn't matter right? because those integers exist (by theorem)
     
    Last edited: Feb 7, 2008
  2. jcsd
  3. Feb 6, 2008 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    The easiest way to prove it is to use unique prime factorization. If gcd(a,b)=1 then a and b have no common prime factors. Ditto for a and c. The set of prime factors of bc is the union of the set of prime factors of b and c. If a has none in common with b and none in common with c, doesn't that prove it has none in common with bc?
     
    Last edited: Feb 7, 2008
  4. Feb 6, 2008 #3
    i see what you're saying and it makes sense

    but we have not gone over that topic in class, and that was not introduced in any of the proofs in the book

    even though that is the easiest way, is there another method to do so?

    actually i skimmed through the book, and i see it's in the upcoming section

    i doubt that my professor would allow me to use an idea from a chapter we will be discussing later
     
    Last edited: Feb 6, 2008
  5. Feb 6, 2008 #4
    what about this other approach: using the definition of GCD

    d=gcd(a,b) if d satisfies the 2 following conditions

    1) d|a and d|b
    2) IF c|a and c|b --> c less than equal to d

    1) is clearly true, since 1 divides any integer
    2) i guess the hard part is to show that c is less than or equal to 1


    Or I believe this is the correct approach

    d = gcd(a,b) iff and only if d satisfies

    1) d|a and d|b
    2) if c|a and c|b --> c|d

    nevermind, this last approach doesn't work, because by hypothesis, c neither divides a nor b
     
    Last edited: Feb 6, 2008
  6. Feb 6, 2008 #5

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Ok, gcd(a,b)=1 means that there are k1 and k2 such that k1*a+k2*b=1. gcd(a,c)=1 means there are l1 and l2 such that l1*a+l2*c=1. Multiply the two together and find m1 and m2 such that m1*a+m2*b*c=1.
     
    Last edited: Feb 7, 2008
  7. Feb 7, 2008 #6
    i see, that's the final step missing

    i said since
    (a,b) = 1 --> 1 = ax + by
    (a,c) = 1 --> 1 = af + cg
    By Theorem, x,y,f, and g exist

    1 = 1.1 = (ax+by)(af+cg) = a^2xf + axcg + aabyf + bycg
    = a(axf + xcg + byf) + bc(yg)
    therefore let

    u = axf + xcg + byf
    and
    v = yg

    and since, all the "letters" used exist and are integers, they satisfy the domain, and the proposition

    is that correct? even though "u" is messy, it doesn't matter right? because those integers exist (by theorem)
     
    Last edited: Feb 7, 2008
  8. Feb 7, 2008 #7

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    That's correct. axf+xcg+byf is just as much of an integer as x is. It doesn't matter that it's "messy".
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?