A property of GCD (Greatest Common Divisor)

      We will denote the greatest common divisor of two integers $a$ and $b$ as $gcd(a,b)$. Some authors use $(a,b)$. A definition of $gcd(a,b)$, more generally valid in unitary commutative rings is

 

$d=gcd(a,b) \Leftrightarrow \begin{cases}d\;\mbox{divides}\;a\;\;and \;\;d\;\mbox{divides}\;b&(i)\\if\;d_{1}\;\mbox{divides} \;a\;and\;d_{1}\;\mbox{divides}\;b\;\;then\;\;d_{1}\;\mbox{divides}\;d&(ii)\end{cases}$ 

        Words $\underline{divides}$ means, in expresions "$d\;divides \;a$" etc, that

"there are an element $x$ in ring $\mathbb{Z}$ such that $d\cdot x=a$" etc.

We will denote "$d\;divides \;a$" by $d\mid a$.

 

     LEMMA If $gcd(c,b)=1$ then $gcd(a,b)=gcd(a\cdot c,b)$

 

Proof. Let $d=gcd(a,b)$; we have $d\mid a$ so $d \mid a\cdot c$. Thus, first

$d \mid a\cdot c$  and   $d \mid b  $  (i')

Secondly, let $\delta$ be such that

(1)                           $\delta \mid a\cdot c$  and  $\delta \mid b$.

$gcd(c,b)=1\Rightarrow$ there are integers $u$ and $v$ such that

(2)                                 $c\cdot u+b \cdot v =1$.

From $\delta \mid b \Rightarrow \delta \mid b\cdot v$  $\overset{(2)}{\Rightarrow} \delta \mid 1-c \cdot u \Rightarrow \delta \mid a-a\cdot c \cdot u \overset{(1)}{\Rightarrow} \delta \mid a$.

     Thus, (1) $\Rightarrow \delta \mid a$ and $\delta \mid b$ so that , via (ii) from definition,

$\delta \mid d$. Finally

$(1) \Rightarrow \delta \mid d$  (ii')

that means - from (i') and (ii"), $d=gcd(a,b)$.

 

 

$\blacksquare$

Remark. Here are another discussion about such phaenomena.