# gcd Lemma

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

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

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