Classical Algebra

Posted Problem Solution

Monday, September 24, 2007

There was a request in today's class to present a solution to the problem taken from the course text, p. 52, that follows. (I did not want to devote in-class time to it.)

Problem.   If $\left(a,b\right)=1$ and $c$ is an integer, then there is some integer $m$ so that $$\left(a+bm,c\right)=1\text{.}$$

Solution. Since $\left(a,b\right)=1$, by “Bezout's Identity” every integer is an integer linear combination of $a$ and $b$. In particular, there are integers $r,s$ such that $$c=ar+bs\text{.}$$

The mechanism that is used to show that the greatest common divisor of two successive remainders in the Euclidean algorithm stays unchanged through the steps of the algorithm may be described as the principle that for any integers $x$, $y$, and $q$ one has the identity $$\begin{array}{cc}\text{(*)}& \left(x,y\right)=\left(y,x-qy\right)\text{.}\end{array}$$ Then, using this principle, for any $m$, one has: $$\begin{array}{cccc}& \hfill \left(c,a+bm\right)& \hfill =\hfill & \left(ar+bs,a+bm\right)\hfill \\ & \hfill & \hfill =\hfill & \left(a+bm,\left(ar+bs\right)-r\left(a+bm\right)\right)\text{by (*)}\hfill \\ & \hfill & \hfill =\hfill & \left(a+bm,b\left(s-m\right)\right)\hfill \end{array}$$ Now choose $m$ so that $s-m=1$, i.e., take $m=s-1$. Then $$\begin{array}{cccc}& \hfill \left(c,a+bm\right)& \hfill =\hfill & \left(a+bm,b\right)\hfill \\ & \hfill & \hfill =\hfill & \left(b,\left(a+bm\right)-mb\right)\text{by (*)}\hfill \\ & \hfill & \hfill =\hfill & \left(b,a\right)\hfill \\ & \hfill & \hfill =\hfill & 1\hfill \end{array}$$