Results 1 to 3 of 3

Math Help - GCD Proof

  1. #1
    Super Member Aryth's Avatar
    Joined
    Feb 2007
    From
    USA
    Posts
    652
    Thanks
    2
    Awards
    1

    GCD Proof

    My professor proposed a question in class awhile ago and told us to prove it for homework. When he proved it in class the day it was due, he gave a very long and unnecessary proof. My proof was significantly shorter and when I asked my professor if my proof was correct he told me to go away, so, since I have such a helping professor, I have to know if this proof is correct so that I can study for the exam later on using the right information. Here's the statement:

    If a,b > 0, then (a,b) = (a + b, [a,b])

    Where (,) is the gcd and [,] is the lcm.

    Proof:

    Suppose there are two integers s and t s.t.

    p^s || a and p^t || b

    This implies that:

    a = mp^s

    b = np^t

    Where p \not | mn

    Without loss of generality, assume s \leq t,

    a + b = mp^s + np^t
    = p^s(m + np^{t -s})

    This implies that p^s || (a + b)

    We know that p^{max(s,t)} || [a,b] since p^{max(s,t)} is the lcm by definition, and that max(s,t) = t

    This implies that p^t || [a,b]

    Therefore

    p^{min(s,t)} || (a + b, [a,b]), where p^s || a + b and p^t || [a,b]

    and p^{min(s,t)} || (a,b) by definition. Since they both are exactly divisible by the same power of p, they must be equal.

    Thanks for the help.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member JaneBennet's Avatar
    Joined
    Dec 2007
    Posts
    293
    I’m not sure what you are doing in your proof myself – but I have a proof which is even shorter than yours. Use the following result:

    If \gcd(m,n)=1, then \gcd(m+n,mn)=1.

    It’s not difficult to prove it. You might like to try it as an exercise.

    So, to the question you are asking.

    Let \gcd(a,b)=d,\ a=a'd,\ b=b'd.

    Then a+b=(a'+b')d,\ \mathrm{lcm}(a,b)=\frac{ab}d=a'b'd; also \gcd(a',\,b')=1.

    \therefore\ \gcd(a+b,\,\mathrm{lcm}(a,b))

    =\ \gcd\left((a'+b')d,\,a'b'd\right)

    =\ d\cdot\gcd(a'+b',a'b')

    =\ d

    =\ \gcd(a,\,b)
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member Aryth's Avatar
    Joined
    Feb 2007
    From
    USA
    Posts
    652
    Thanks
    2
    Awards
    1
    I did forget two things:

    1. p is prime

    2. If p^q | a and p^{q+1} \not | a, then p^q divides a exactly, denoted p^q || a.

    We were supposed to prove it using prime numbers. The proof you provided was the one we all wished we could use.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 5
    Last Post: October 19th 2010, 10:50 AM
  2. Replies: 0
    Last Post: June 29th 2010, 08:48 AM
  3. [SOLVED] direct proof and proof by contradiction
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 27th 2010, 10:07 PM
  4. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: June 8th 2008, 01:20 PM
  5. proof that the proof that .999_ = 1 is not a proof (version)
    Posted in the Advanced Applied Math Forum
    Replies: 4
    Last Post: April 14th 2008, 04:07 PM

Search Tags


/mathhelpforum @mathhelpforum