GCD prof

**Syndicate01** · April 20th 2010, 07:04 AM

I need a little help on this one.....Prove that GCD(a,b) = GCD(b, a+b).

**Drexel28** · April 20th 2010, 07:25 AM

Originally Posted by Syndicate01

I need a little help on this one.....Prove that GCP(a,b) = GCD(b, a+b).

Suppose that $d\mid a,b$ then $d\mid a+b\implies d\mid a,a+b$ so $(b,a+b)\mid (a,b)$ . Work simillarly

**Bruno J.** · April 20th 2010, 08:10 AM

In general, $\mbox{GCD}(a,b) = \mbox{GCD}(\alpha a+\beta b,\gamma a + \eta b)$ for any matrix $\begin{pmatrix} {\alpha}&{\beta}\\ {\gamma}&{\eta} \end{pmatrix} \in \mbox{SL}_2(\mathbb{Z})$ .

**Syndicate01** · April 20th 2010, 08:33 AM

Originally Posted by Bruno J.

In general, $\mbox{GCD}(a,b) = \mbox{GCD}(\alpha a+\beta b,\gamma a + \eta b)$ for any matrix $\begin{pmatrix} {\alpha}&{\beta}\\ {\gamma}&{\eta} \end{pmatrix} \in \mbox{SL}_2(\mathbb{Z})$ .

Heu ...