Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I need to prove some GCD properties:

$i$) $\quad\gcd(a,b)=\gcd(b,a)$
$ii$) $\quad\gcd(ca,cb)=c\gcd(a,b)$
$iii$) $\quad\gcd(\gcd(a,b),c)=\gcd(a,\gcd(b,c))$

Proof $(i)$:
Let $d=\gcd(a,b)\,\Rightarrow\,d|a\quad\text{and}\quad d|b\,\Rightarrow\,d|b\quad\text{and}\quad d|a\,\Rightarrow\,d|\gcd(b,a)\Leftrightarrow \gcd(a,b)|\gcd(b,c)$

let $e=\gcd(b,c)\,\Rightarrow\,e|b\quad\text{and}\quad e|a\,\Rightarrow\,e|a\quad\text{and}\quad e|b\,\Rightarrow e|\gcd(a,b)\Leftrightarrow \gcd(b,c)|\gcd(a,b)$
therefore $\gcd(a,b)=\gcd(b,c)$

Proof $(ii)$:
Let $d=\gcd(a,b)\Rightarrow\, d|a,d|b\,\Rightarrow\, cd|ca,cd|cb\Rightarrow\,cd|\gcd(ca,cb)\,\Rightarrow\, c\cdot\gcd(a,b)|\gcd(ca,cb)$

Let $e=\gcd(ca,cb)\,\Rightarrow\,e|ca\,,\,e|cb\,\Rightarrow\, e|cax+cby\,\Rightarrow\, e|cd\,\Rightarrow\,\gcd(ca,cb)|c\cdot\gcd(a,b)$
therefore $\gcd(ca,cb)=c\cdot\gcd(a,b)$

Proof $(iii)$:
Let $d=\gcd(\gcd(a,b),c)\,\Rightarrow\, d|\gcd(a,b)\,,\, d|c\,\Rightarrow\, d|a\,,\,d|b\,,\,d|c\Rightarrow\,d|a\,,\,d|\gcd(b,c)\,\Rightarrow\,d|\gcd(a,\gcd(b,c))\,\Rightarrow\,\gcd(\gcd(a,b),c)|\gcd(a,\gcd(b,c))$

Let $e=\gcd(a,\gcd(b,c))\,\Rightarrow\, e|\gcd(b,c)\,,\, e|a\,\Rightarrow\, e|a\,,\,e|b\,,\,e|c\Rightarrow\,e|\gcd(a,b)\,,\,e|c\,\Rightarrow\,e|\gcd(\gcd(a,b),c)\Rightarrow\,\gcd(a,\gcd(b,c))|\gcd(\gcd(a,b),c)$
terefore $\gcd(a,\gcd(b,c))=\gcd(\gcd(a,b),c)$

I have no experience in proving gcd, so i hope that someone can give me some advice/tips/etc

share|improve this question
    
Looks good to me, there is a small typo in the proof of $(i)$: should be $e=gcd(b,a)$. –  N. S. Nov 11 '12 at 20:05

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.