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!

Greatest Common Divisor Proof

  1. Apr 2, 2012 #1
    1. The problem statement, all variables and given/known data

    Suppose a, b ∈ N and a|b. Prove that a = gcd(a, b).

    2. Relevant equations
    Seems easy intuitively but actually proving it is giving me problems.


    3. The attempt at a solution
    I have been trying to use the fact that gcd(a,b)=na + mb here m and n are integeres but got stuck.
     
  2. jcsd
  3. Apr 2, 2012 #2
    Well we clearly have a|a and a|b, and the largest divisor of a number is itself. This should follow immediately.
     
  4. Apr 2, 2012 #3
    Yeah and i understand that but we are asked to prove it, not explain why.
     
  5. Apr 2, 2012 #4
    Well you can probably prove by contradiction that the largest divisor of a number is itself. I mean a|b => a=gcd(a,b) is so trivial that there's very little to say, how formal does your professor expect your proof to be? You can take it all the way down to pure logic if you really wanted to.
     
  6. Apr 2, 2012 #5
    The difference between a proof and an explanation actually becomes increasingly fuzzy the farther you get in math.
     
  7. Apr 2, 2012 #6

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    A proof of this is certainly possible.

    But first, we would have to know how exactly you defined a|b and gcd(a,b).
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Greatest Common Divisor Proof
Loading...