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: Greatest common divisor proof

  1. Apr 20, 2017 #1
    I need opinion about this problem.
    question :Prove:
    If(a,b)= l and if ( "(a,b)=1" mean greatest common divisor of integers and b is 1 )
    c|a (c divides a)
    d|b (d divides b )
    (c,d)= 1. ( "(c,d)=1" mean greatest common divisor of integers and b is 1 ) <-- this need to be proved.
    (Is that following a good proof ?)
    Then there are 2 sets A and B.
    divisors of a ∈ A <-- do this need be proved too?
    divisors of b ∈ B

    A ∩ B = 1

    c ⊂ A
    d ⊂ B

    c ∩ b = 1 which is what we are looking for.

    Thank you.
  2. jcsd
  3. Apr 20, 2017 #2


    User Avatar
    Homework Helper

    You are correct when you say you can consider the sets ##A,B## containing the divisors of ##a##, resp. ##b##. You don't need to prove that. You know that such a set always exists.

    However, when you write ##A \cap B = 1##, this is bad notation. You either write ##A \cap B = \{1\}## or ##|A \cap B | = 1##. I don't know what exactly you mean by this, but either way you must explain why this is true.

    You also wrote ##c \cap d = 1## which doesn't make sense as ##c,d## are elements and not sets.
  4. Apr 20, 2017 #3
    Then there are 2 sets A and B.
    divisors of a ∈ A
    divisors of b ∈ B

    A ∩ B = {1} <-- this is just restating the fact that 'a' and 'b' has only gcd which is "1" I am trying to say the divisor set A and divisor set be B has only one common element with is "1"

    c ∈ A <--because 'c' divide 'a' that means its part of 'A' set of all the divisor of a
    d ∈ B < -- same reason as above

    C ={ all the divisor of c }
    D ={ all the divisor of d }

    C ⊂ A because a is one of the multiples of c. is this need to proved ?
    D ⊂ B same reason as above.

    we know A ∩ B = {1}
    since C ⊂ A and D ⊂ B

    C ∩ D ={1}
    Which means the only common divisor of c and d is '1'
  5. Apr 20, 2017 #4


    User Avatar
    2017 Award

    Staff: Mentor

    You can prove it, but I guess your course did that earlier already - it is one of the basic features of divisibility.
  6. Apr 20, 2017 #5
    So I have proved it properly ?
    Please tell.

    Thank you.
  7. Apr 20, 2017 #6


    User Avatar
    2017 Award

    Staff: Mentor

    I'm not the person grading your homework. I think it is okay, but I cannot know if the person grading your homework wants to see more steps in between.

    I moved the thread to our homework section, by the way.
  8. Apr 20, 2017 #7
    Its not home work, I am judging my self before taking a analysis course. That will be my first ever math course.
    This problem is from the book I will be using.
    That is why I was keen to know.
    Thank you.
  9. Apr 20, 2017 #8


    User Avatar
    Science Advisor
    Homework Helper

    i would just show directly that if x divides both c and d, then x also divides both a and b, hence x = ±1.
  10. Apr 20, 2017 #9
    Curious - what's the name/author of the book?
  11. Apr 20, 2017 #10
    Introduction to Analytic Number Theory
    by Tom M. Apostol

    BTW, what I posted is not how this book deals with things.
    I once read a book, a few chapters, "introduction to topology".
    So I remembered some set language.

    In t Apostol's book I have read only few pages, I tried this problem from Apostol's book because It looked like it could have been done, before reading stuff from the book.
    Last edited by a moderator: May 8, 2017
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted