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: Proof About Greatest Common Divisors

  1. May 17, 2013 #1
    1. The problem statement, all variables and given/known data
    Disprove the following assertion: "There exist distinct positive integers a and b such that for all natural numbers n we have (a,n)=1 or (b,n)=1."

    2. Relevant equations
    (a,n)=1 and (b,n)=1 means greatest common divisor of a and n is 1, and of b and n is 1, respectively.

    3. The attempt at a solution

    This was my attempt at a solution. My teacher said it was wrong. Not really sure why.

    Suppose there exists such a and b that are natural numbers where a isn't equal to b, a and b aren't equal to 1, where for all n that are natural numbers we have (a,n)=1 or (b,n)=1. Since a isn't equal to 1, we have that there's a prime divisor of a, i.e. p1=P. Since b isn't equal to 1, we have that there's a prime divisor of b, i.e. p2=P. Take n=p1*p2. Then p1 divides (a,n) where (a,n)>1, and p2 divides (b,n) where (b,n)>1 which is a contradiction.
    1. The problem statement, all variables and given/known data

    2. Relevant equations

    3. The attempt at a solution
  2. jcsd
  3. May 17, 2013 #2
    If there is a prime divisor p1 of a, then wouldn't (a, p1) = p1?
  4. May 17, 2013 #3


    User Avatar
    Science Advisor

    Have you considered the cases n= a and n= b?
  5. May 17, 2013 #4
    In those cases then (a,n) and b,n)=n wouldn' they? In our book it gives a hint that says "try finding the smallest such counterexample when a=2 and b=5. How does this suggest that we construct a counterexample in general?"

    If a=2 and b=5, then (a,n)=1 if and only if n was an odd number (aka not a multiple of 2). If b=5, (b,n)=1 if and only if n wasn't divisible by 5. I'm just confused. I don't see how the hint helps me.
  6. May 17, 2013 #5
    Aha I somewhat got it. Not sure how to actually prove it though. The assertion only works for a=b=1 because any number larger than 1 has a natural number associated with it which share a greatest common divisor. For example, let a=10. Then n could be 10 also and then (a,n,)=10
  7. May 17, 2013 #6


    User Avatar
    Homework Helper

    What is (b,n) when n = 10?
  8. May 17, 2013 #7
    Nevermind guys I got it. The assertion is actually true when either a or b (not both) equals 1. The book tricked me by saying disprove the assertion when is reality the assertion is really true.

    let's say a=1 then (a,n)=1 and it doesn't matter what positive integer b is (as long as its not 1), then the assertion holds.
  9. May 17, 2013 #8


    User Avatar
    Homework Helper

    Hmm, perhaps the question should have been,

    Disprove: There exist integers 1 <= a < b such that, for every natural number n, (a,n) = 1 or (b,n) = 1.

    But, daneault23, you answered the question as posed so good job.
  10. May 17, 2013 #9
    Tricky books these days lol
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted