1. Limited time only! Sign up for a free 30min personal 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!

Homework Help: Relatively prime

  1. Feb 10, 2014 #1
    1. The problem statement, all variables and given/known data
    For integers a,b, and c, if a and c are relatively prime and c|ab, then c|b.
    Knowing that: For any integers p and q, there are integers s and t such that gcd(p,q) = sp + tq.

    The hint I'm given is that I should form an equation from the fact that they are "relatively prime."
    The last caveat is that I cannot use fractions at all in my proof.
    2. Relevant equations

    3. The attempt at a solution
    So my hang up is definitely the equation for relatively prime. As I understand it for relatively prime: gcd(a,c)=1. Then, I suppose I could just use the given equation to say that 1= sa + tc. (I believe this Bézout's identity).

    Then I have the following claim: If 1= sa + tc and ab=cn then b=cp. Where n and p are just integers. Then I can say that sa=1-tc. Then multiplying the second condition by 's' I'd have sab=scn. Combining them b(1-tc)=scn.

    But I can't do fractions so I'm not sure what to make of this, or if I've even started the problem correctly. I find it unlikely that my relatively prime equation is correct, or is what they intended me to do.

    Thanks for the suggestions.
  2. jcsd
  3. Feb 11, 2014 #2

    Simon Bridge

    User Avatar
    Science Advisor
    Homework Helper

    so you mean you have to prove
    if gcd(c,a)=1
    and gcd(c,ab)=1
    then gcd(c,b)=1

    I don't see how you got ab=cn.
    Go thorugh it more cereafully: express each of the lines using Bezouts ID... you end up with three similar looking expressions. don't forget the entire identity.
  4. Feb 11, 2014 #3
    Maybe the way we write things is different.
    gcd(c,a)=1 is relatively prime
    c|ab means that ab is divisible by c. Or, written another way c(n)=ab where n is just some integer.
    And, of course c|b just means that b is divisible by c or c(p)=b.

    I'm not sure if you understood me or if I don't understand you.
  5. Feb 11, 2014 #4
    Well, I think I've got it. I had to do one operation to rearrange an equation that may/may not be seen as division but I think I'm safe. Thanks for the help anyway.
  6. Feb 11, 2014 #5

    Simon Bridge

    User Avatar
    Science Advisor
    Homework Helper

    Oh I see - right... c|ab would be nc=ab: n is an integer.
    In this example, everything is an integer - so combinations of them that do not involve division are also integers.

    ...so you need only show that nc=ab and sc+ta=1 both being true means that b = [some integer]c.
    Whatever ends up in the brackets will be an integer so long as it does not include a division: i.e. that's not a restriction, it's a hint!

    Looking back at post #1: you got stuck at:

    ... all you need from there is to do some algebra so that you get

    b = [some stuff]c

    ... then check that the [some stuff] is an integer.
  7. Feb 11, 2014 #6
    You are almost there, play around with this equation.
  8. Feb 11, 2014 #7
    Yeah, I was able to multiply that equation with a another variable and combine everything so that the b was able to come out and everything else became an integer on the other side. The trick to this was just figuring out what to multiply what by.
  9. Feb 11, 2014 #8
    You seem to be working too hard.

    b(1-tc) = b - btc.
  10. Feb 11, 2014 #9
    I suppose I could say ##b-btc=scn \implies b=scn+btc \implies b=c(sn+bt)## I saw this and was a little hesitant because I wasn't sure about having the 'b' in there with the other integers. I mean the quantity could be anything but is still dependent on 'b'. I'm not sure it really matters or not, though.
  11. Feb 11, 2014 #10

    Simon Bridge

    User Avatar
    Science Advisor
    Homework Helper

    When you have done this sort of algebra in the past, you are usually asked to find an actual value for b or c or whatever - so it is not helpful to mix up variables like that.

    In this case it does not matter because you only need the relationship b=[some integer]c - you are not trying to find out what that integer is or what any of the values are. All you care about is that it is an integer.
  12. Feb 11, 2014 #11
    It is perfectly ok for b to be in there with the other integers .

    For example 6 = 2(3*3 - 6*1). Here b = 6 and c = 2.
  13. Feb 12, 2014 #12
    I've updated my proof with this. It is certainly far easier to do than the shenanigans I used before. While what I had should have been correct it took a very long time to get there.

    I originally thought this was going to end up being the way things worked out but as soon as I got that b on the right side I just thought it looked to weird. I struggled with this for a couple days off and on trying to find a way to make it work without having b over there; and all this time I really had the problem all but finished if I had just done what I originally wanted to do.

    Thanks a lot for the help!
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted