Results 1 to 3 of 3

Math Help - gcd Lemma

  1. #1
    Newbie Demandeur's Avatar
    Joined
    Jun 2010
    Posts
    14

    gcd Lemma

    Prove that if a = qb+r for q, b, r \in \mathbb{Z}, then \gcd(a, b) = \gcd(b, r).

    Let n be any common divisor of a and b. Then we have n\mid{a} and n\mid{b} therefore n\mid{a-qb} \Rightarrow n\mid{r}. Similarly, let m be any common divisor of b and r. Then we have m\mid{b} and m\mid{r} therefore m\mid{qb+r} \Rightarrow m\mid{a}. How does it follow that a, b and b, r have the same common divisors?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Rhymes with Orange Chris L T521's Avatar
    Joined
    May 2008
    From
    Santa Cruz, CA
    Posts
    2,844
    Thanks
    3
    Quote Originally Posted by Demandeur View Post
    Prove that if a = qb+r for q, b, r \in \mathbb{Z}, then \gcd(a, b) = \gcd(b, r).

    Let n be any common divisor of a and b. Then we have n\mid{a} and n\mid{b} therefore n\mid{a-qb} \Rightarrow n\mid{r}. Similarly, let m be any common divisor of b and r. Then we have m\mid{b} and m\mid{r} therefore m\mid{qb+r} \Rightarrow m\mid{a}. How does it follow that a, b and b, r have the same common divisors?

    Well, by definition of the gcd, \exists\,m,n\in\mathbb{Z}: \gcd(a,b)=am+bn.

    Since a=bq+r for some b,q,r\in\mathbb{Z}, we see that

    \begin{aligned}\gcd(a,b) &= am+bn\\ &=(bq+r)m+bn\\ &=b(qm+n)+rm \end{aligned}

    Since qm+n,m\in\mathbb{Z}, we now see that b(qm+n)+rm=\gcd(b,r).

    Does this make sense?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Jun 2010
    From
    Israel
    Posts
    148
    Quote Originally Posted by Demandeur View Post
    Prove that if a = qb+r for q, b, r \in \mathbb{Z}, then \gcd(a, b) = \gcd(b, r).

    Let n be any common divisor of a and b. Then we have n\mid{a} and n\mid{b} therefore n\mid{a-qb} \Rightarrow n\mid{r}. Similarly, let m be any common divisor of b and r. Then we have m\mid{b} and m\mid{r} therefore m\mid{qb+r} \Rightarrow m\mid{a}. How does it follow that a, b and b,  r have the same common divisors?

    When you wrote "therefore  n\mid{a-qb} \Rightarrow n\mid{r}" you should also notice that n|b (by hypothesis). The same thing for m . You should also note that m|b (by hypothesis).
    Now what you have is that if n is a common divisor of a and b , then it's also of b and r . Similarly, if  m is a common divisor of b and  r, then it's also of b and a .
    Therefore, the pair a,b has the same common divisors as the pair b,r . In particular, the greatest common divisor.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Hensel's lemma
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 11th 2010, 06:26 PM
  2. Pumping Lemma
    Posted in the Advanced Math Topics Forum
    Replies: 0
    Last Post: October 25th 2010, 08:52 AM
  3. Proof of a lemma
    Posted in the Pre-Calculus Forum
    Replies: 1
    Last Post: April 29th 2009, 05:19 AM
  4. Pumping Lemma
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: April 28th 2009, 12:41 PM
  5. Ito's Lemma
    Posted in the Advanced Statistics Forum
    Replies: 2
    Last Post: June 25th 2008, 10:29 PM

Search Tags


/mathhelpforum @mathhelpforum