# Math Help - GCD proofs

1. ## GCD proofs

I need to prove the following:

1. Let $a,b,d\in\mathbb{Z}$

If $d|a$ and $d|b$, then:

$d=gcd(a,b) \Leftrightarrow (\frac{a}{d},\frac{b}{d})=1$

Here I was able to prove only one direction:

$d=gcd(a,b) \Rightarrow (\frac{a}{d},\frac{b}{d})=1$

Since $d=gcd(a,b)$, there exist $s,t\in\mathbb{Z}$ such that $d=sa+tb$.
I divide the whole thing by d and get:
$s\frac{a}{d}+t\frac{b}{d}=1$

Now since $gcd(x,y)=\min_{u,v\in\mathbb{Z}}}\left \{ xu+yv\in\mathbb{N}} \right \}$, and 1 is the minimal natural number, then $gcd(\frac{a}{d},\frac{b}{d})=1$.

2. $gcd(ab,ac)=a\cdot gcd(b,c)$

Here I don't have a clue what to do.

any help would be greatly appreciated!

2. ## Re: GCD proofs

For 2, use what you proved in part 1. For part 1, it looks like you got the answer already. Just do the proof in the opposite direction.

Assume $\left(\dfrac{a}{d},\dfrac{b}{d}\right) = 1$. Then there exist integers $s,t$ such that $s\dfrac{a}{d} + t\dfrac{b}{d} = 1$. Then multiply both sides by $d$. Now, $(a,b) \le d$ and since $d|a$ and $d|b$, $(a,b) \ge d$.

3. ## Re: GCD proofs

Thanks, SlipEternal.

Originally Posted by SlipEternal
Now, $(a,b) \le d$ and since $d|a$ and $d|b$, $(a,b) \ge d$.
I get why $d|a$ and $d|b$ $\Rightarrow$ $(a,b) \ge d$, but why is $(a,b) \le d$?

edit*
OK, I couldn't think of a way to use 1 to prove 2, but I came up with something else for 2...:

$gcd(ab,ac)=\min_{u,v\in\mathbb{Z}}\left \{ u(ab)+v(ac)\in\mathbb{N} \right \}=\min_{u,v\in\mathbb{Z}}\left \{ a(ub+vc)\in\mathbb{N} \right \}=$
$a\cdot\min_{u,v\in\mathbb{Z}}\left \{ ub+vc\in\mathbb{N} \right \}=a\cdot\gcd(b,c)$

Hope it's valid...
Nonetheless, if you have some other way, I would love to see.

4. ## Re: GCD proofs

Originally Posted by Stormey
I get why $d|a$ and $d|b$ $\Rightarrow$ $(a,b) \ge d$, but why is $(a,b) \le d$?
Because after you multiply out by $d$, you get $sa+tb = d$, and $(a,b) = \min_{u,v \in \mathbb{Z}} \{ua+vb \in \mathbb{N}\} \le sa+tb = d$.

Originally Posted by Stormey
edit*
OK, I couldn't think of a way to use 1 to prove 2, but I came up with something else for 2...:

$gcd(ab,ac)=\min_{u,v\in\mathbb{Z}}\left \{ u(ab)+v(ac)\in\mathbb{N} \right \}=\min_{u,v\in\mathbb{Z}}\left \{ a(ub+vc)\in\mathbb{N} \right \}=$
$a\cdot\min_{u,v\in\mathbb{Z}}\left \{ ub+vc\in\mathbb{N} \right \}=a\cdot\gcd(b,c)$

Hope it's valid...
Nonetheless, if you have some other way, I would love to see.
You would need to explain in words why you are able to factor a number from a set, but yes. That proof would work. To use part (1) to prove part (2):

\begin{align*}& \gcd(b,c) = \gcd(b,c) \\ \Leftrightarrow & \gcd\left(\dfrac{b}{\gcd(b,c)},\dfrac{c}{\gcd(b,c) }\right) = 1 \\ \Leftrightarrow & \gcd\left(\dfrac{ab}{a\cdot \gcd(b,c)},\dfrac{ac}{a\cdot \gcd(b,c)}\right) = 1 \\ \Leftrightarrow & \gcd(ab,ac) = a\cdot \gcd(b,c)\end{align*}.

I start with an obviously true statement. By part (1), that is true if and only if the second expression is true. Multiplying top and bottom of each fraction by $a$ gives the third, and to get to the fourth expression, we just need to check that $a\cdot \gcd(b,c) | ab$ and $a\cdot \gcd(b,c) | ac$. Those are obviously true, so again by part (1), the third biconditional implies the fourth expression. Since the first expression is true, the last expression is true.

5. ## Re: GCD proofs

Great. once again, thanks!

6. ## Re: GCD proofs

And just a note: I'm learning a lot from your posts.

7. ## Re: GCD proofs

Oh, and I didn't state it, but there are some cases that you might want to check. For part (1), $a=b=0$ is a weird case for $\gcd(a,b)$, so depending on your definitions, you may need to check it separately. Some mathematicians say $\gcd(0,0)$ is undefined. Some say it is zero (useful if you want to look at the natural numbers as a distributive lattice with $\text{lcm}$ and $\gcd$ as join and meet respectively). If using the extended integers, it would be $\infty$. So, if your book defines it, you need to check it. Since $\{s\cdot 0 + t\cdot 0 \in \mathbb{N} \mid s,t \in \mathbb{Z}\} = \emptyset$ if $0\notin \mathbb{N}$, it may be undefined in your book. If it is defined as zero (or if your book uses the convention that $0 \in \mathbb{N}$), then the check is easy. Zero does not divide zero, so the statement is automatically true.

For part (2), again, if your book defined $\gcd(0,0)=0$, you need to check the case when $a=0$ or when $b=c=0$ separately. Note for (2), it is false if $a<0$. Writing it $\gcd(ab,ac) = |a|\cdot \gcd(b,c)$ would make it true for $a<0$, as well. And if $\gcd(0,0) = 0$, it is easy to show that $\gcd(0b,0c) = \gcd(0,0) = 0 = 0\cdot \gcd(b,c)$.