1. ## gcd proofs

Hi all, have a couple of gcd proofs that I'm stuck with.

1=If gcd(a,c)=1 and gcd(b,c)=1 then gcd(ab,c)=1

thus far all I can figure is to do the following linear combos:
1- ax+cy=1
2-bu+cv=1
3-abz+ct=1
But then I don't know what to do. I try solving for c in one of them and then substituting, but this leads nowhere.

2- If a|c and b|c and gcd(a,b)=1 then ab|c.
This is similar to 1, so I'm also stuck with this one.

Any help would be appreciated. Thanks!

2. Originally Posted by jusstjoe
Hi all, have a couple of gcd proofs that I'm stuck with.

1=If gcd(a,c)=1 and gcd(b,c)=1 then gcd(ab,c)=1

thus far all I can figure is to do the following linear combos:
1- ax+cy=1
2-bu+cv=1
3-abz+ct=1
But then I don't know what to do. I try solving for c in one of them and then substituting, but this leads nowhere.

2- If a|c and b|c and gcd(a,b)=1 then ab|c.
This is similar to 1, so I'm also stuck with this one.

Any help would be appreciated. Thanks!
Hi jusstjoe.

(1) You have

$\displaystyle ax+cy\ =\ 1$
$\displaystyle bu+cv\ =\ 1$

Now multiply them together:

$\displaystyle 1\ =\ (ax+cy)(bu+cv)\ =\ ab(ux)+c(avx+buy+cvy)$

Thus $\displaystyle \gcd(ab,c)=1.$

(2) If $\displaystyle \gcd(a,b)=1,$ then $\displaystyle \mathrm{lcm}(a,b)=ab.$ The rest follows from the definition of LCM.
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}