Is my proof for $\gcd(ab,c) \leq \gcd(b,c)\gcd(a,c)$ incorrect?

41 Views Asked by At

I tried to do the proof above but am not sure if what I did was actually correct.

$a,b,c \in \mathbb N$

First, suppose $\gcd(ab,c) = d$, where d is some positive integer

Then $abx + cy = d$

Rewrite $bx = w$; $aw + cy = d$

So $\gcd(a,c) = d$

Moreso, we can rewrite $abx + cy = d$ to get $\gcd(b,c) = d$

So we know when $d = 1 $ that $\gcd(ab,c) = \gcd(b,c)\gcd(a,c)$

and when $d > 1 $ that $\gcd(ab,c) < \gcd(b,c)\gcd(a,c)$

therefore $\gcd(ab,c) \leq \gcd(b,c)\gcd(a,c)$

1

There are 1 best solutions below

1
On

There is a problem saying $\gcd(a, c) = d$, because by you would only know $\gcd(a, c) \mid d$ by $aw + cy = d$.

An easy counterexample: consider $a = 1, b = 2, c = 2$, we have $d = \gcd(ab, c) = 2$, but $gcd(a, c) = 1 \neq d$.

Instead, you can try to prove $\gcd(ab, c) \mid \gcd(b, c) \gcd(a, c)$ by considering the prime factorization.