Results 1 to 3 of 3

Thread: gcd Lemma

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

    gcd Lemma

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

    Let $\displaystyle n$ be any common divisor of $\displaystyle a$ and $\displaystyle b$. Then we have $\displaystyle n\mid{a}$ and $\displaystyle n\mid{b}$ therefore $\displaystyle n\mid{a-qb} \Rightarrow n\mid{r}.$ Similarly, let $\displaystyle m$ be any common divisor of $\displaystyle b$ and $\displaystyle r$. Then we have $\displaystyle m\mid{b}$ and $\displaystyle m\mid{r}$ therefore $\displaystyle m\mid{qb+r} \Rightarrow m\mid{a}.$ How does it follow that $\displaystyle a, b$ and $\displaystyle 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
    Chicago, IL
    Posts
    2,844
    Thanks
    5
    Quote Originally Posted by Demandeur View Post
    Prove that if $\displaystyle a = qb+r$ for $\displaystyle q, b, r \in \mathbb{Z}$, then $\displaystyle \gcd(a, b) = \gcd(b, r)$.

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

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

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

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

    Since $\displaystyle qm+n,m\in\mathbb{Z}$, we now see that $\displaystyle 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 $\displaystyle a = qb+r$ for $\displaystyle q, b, r \in \mathbb{Z}$, then $\displaystyle \gcd(a, b) = \gcd(b, r)$.

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

    When you wrote "therefore $\displaystyle n\mid{a-qb} \Rightarrow n\mid{r}" $you should also notice that $\displaystyle n|b $ (by hypothesis). The same thing for $\displaystyle m $. You should also note that $\displaystyle m|b $ (by hypothesis).
    Now what you have is that if $\displaystyle n $ is a common divisor of $\displaystyle a $ and $\displaystyle b $, then it's also of $\displaystyle b $ and $\displaystyle r $. Similarly, if $\displaystyle m $ is a common divisor of $\displaystyle b $ and $\displaystyle r$, then it's also of $\displaystyle b $ and $\displaystyle a $.
    Therefore, the pair $\displaystyle a,b $ has the same common divisors as the pair $\displaystyle 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: Nov 11th 2010, 06:26 PM
  2. Pumping Lemma
    Posted in the Advanced Math Topics Forum
    Replies: 0
    Last Post: Oct 25th 2010, 08:52 AM
  3. Proof of a lemma
    Posted in the Pre-Calculus Forum
    Replies: 1
    Last Post: Apr 29th 2009, 05:19 AM
  4. Pumping Lemma
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Apr 28th 2009, 12:41 PM
  5. Ito's Lemma
    Posted in the Advanced Statistics Forum
    Replies: 2
    Last Post: Jun 25th 2008, 10:29 PM

Search Tags


/mathhelpforum @mathhelpforum