# gcd Lemma

• July 2nd 2010, 03:52 PM
Demandeur
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?
• July 2nd 2010, 04:16 PM
Chris L T521
Quote:

Originally Posted by Demandeur
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?
• July 2nd 2010, 06:24 PM
melese
Quote:

Originally Posted by Demandeur
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.