0

Show that $c|a$ and $c|b$ iff $c|gcd(a,b)$

I am only going to show that the if part is true and i have the solution to this proof just i found the if part of the proof dissatisfying.

since c|a, c|b and $c \le gcd(a,b)$ it follows that there exists an integer $f$ such that $gcd(a,b) = cf$ and hence $c|gcd(a,b)$

If this is not true, could I have some help. please.

  • 1
    One way is to use the Bezout Theorem, which says there exist integers $x$ and $y$ such that $ax+by=\gcd(a,b)$. – André Nicolas Feb 26 '15 at 17:24
  • 3
    "it follows that..." This part makes little sense. You've only concluded that $\gcd(a,b)\leq c$, how did you conclude there exists such an $f$ from this? Or are you assuming a property of $gcd$? What you've written is true but at the same time is not justified. – Alex R. Feb 26 '15 at 17:26
  • Alex, i'm a little unsure how to justify it. I know that it has to be true (or does it?). How would i justify? –  Feb 26 '15 at 17:34
  • How are you defining the gcd? – Reveillark Feb 26 '15 at 17:41
  • gcd(a,b) = au + bv, I have used this to prove the 'only if' part of the proof. I can deduce from c|gcd(a,b) that c|au + bv and hence by a corollary in my text book that c|a and c|b. –  Feb 26 '15 at 17:44
  • Also this; (1) d|a and d|b (2) if c |a and c|b then c $\le$ d where d is the GCD –  Feb 26 '15 at 17:46
  • @HMPARTICLE: If you're not a fan of Bezout's theorem, you could just assume that $c$ has a prime factorization $c=p_1^{a_1}\cdots p_k^{a_k}$, and so does your gcd, along with $a,b$. Show that if $c$ doesn't divide your gcd, then you could throw in the prime factors of $c$ into the gcd to make it even bigger (and still divide $a,b$). – Alex R. Feb 26 '15 at 17:47
  • It's not that i'm not a fan, just don't see how to deduce c|gcd(a,b) from c|a and c|b using Bezout's theorem –  Feb 26 '15 at 17:52

2 Answers2

0

If $c|gcd(a,b)$, then it is easy to see that it divides both $a$ and $b$.

Conversely, suppose that $c|a$ and $c|b$. It follows that there are $p, q \in \Bbb Z$ such that $a = pc$ and $b = qc$.

By Bezout's identity, there exists $\alpha$ and $\beta$ in $\Bbb Z$ such that:

$$\alpha a + \beta b = gcd(a,b)$$

Hence:

$$\alpha(pc) + \beta(qc) = gcd(a,b)$$

Thus:

$$(\alpha p + \beta q)c = gcd(a,b)$$

But, $(\alpha p + \beta q) \in \Bbb Z$. Therefore $c|gcd(a,b)$.

0

Your attempted proof is unsatisfactory in that the "it follows that there exists an integer $f$ statement is merely restating what you set out to prove.

To show the "if" part (which by the way is $c|\text{gcd}(a,b) \Longrightarrow c|a \wedge c|b$) $$ g = \text{gcd}(a,b) \rightarrow \exists\{k_a,k_b\in \Bbb{Z} \}:( a = k_ag) \wedge (b = k_b g)) \\ c|\text{gcd}(a,b) \rightarrow \exists k_c: g = k_c c\\ g = k_cc \rightarrow \frac{a}{k_a}=k_cc \rightarrow a = (k_ak_c)c \rightarrow c|a\\ g = k_cc \rightarrow \frac{a}{k_a}=k_cc \rightarrow a = (k_ak_c)c \rightarrow c|a $$

Mark Fischler
  • 41,743
  • Thanks for clearing that up. I have been saying it backwards since the start. –  Feb 26 '15 at 17:57