Results 1 to 3 of 3

Thread: GCD Proof

  1. #1
    Super Member Aryth's Avatar
    Joined
    Feb 2007
    From
    USA
    Posts
    666
    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 $\displaystyle a,b > 0$, then $\displaystyle (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.

    $\displaystyle p^s || a$ and $\displaystyle p^t || b$

    This implies that:

    $\displaystyle a = mp^s$

    $\displaystyle b = np^t$

    Where $\displaystyle p \not | mn$

    Without loss of generality, assume $\displaystyle s \leq t$,

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

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

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

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

    Therefore

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

    and $\displaystyle 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 $\displaystyle \gcd(m,n)=1,$ then $\displaystyle \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 $\displaystyle \gcd(a,b)=d,\ a=a'd,\ b=b'd.$

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

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

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

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

    $\displaystyle =\ d$

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

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

    1. p is prime

    2. If $\displaystyle p^q | a$ and $\displaystyle p^{q+1} \not | a$, then $\displaystyle p^q$ divides a exactly, denoted $\displaystyle 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: Oct 19th 2010, 10:50 AM
  2. Replies: 0
    Last Post: Jun 29th 2010, 08:48 AM
  3. [SOLVED] direct proof and proof by contradiction
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Feb 27th 2010, 10:07 PM
  4. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: Jun 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: Apr 14th 2008, 04:07 PM

Search Tags


/mathhelpforum @mathhelpforum