Greatest Common Divisor Divisibility

Question

If I have three whole positive numbers $a, b$ and $c.$

If I form the product $a \cdot b$ and that product is divisible by $c.$

How can you prove the following assertion:

If the greatest common divisor of $b$ and $c$ is one, then $a$ must be divisible by $c.$

Answer 1

Change of plan:

Basic tenet: If $\gcd(k,m) = 1$ then $k|N \iff k|Nm$.

Proof: If $k|N \implies k|Nm$ is obvious.

If $k|Nm$ let $p$ be prime so that $p|k$. Then $p|N$ or $p|m$. But we know $p \not \mid m$ so $p|N$. Let $k' = k/p$ and $N' = N/p$. We have $k'|N'm$ and $p|N$.

Do the same argument for $q|k'$ where $q$ is prime (note: it's possible that $p = q$). Then we get $\overline k = k'/q$ and $\overline N = N'/q$ and we have $\overline k|\overline Nm$ and $pq|N$.

Repeat inductively for every prime factor of $k$.

In the final step we'll conclude $1|m$ and $k = pqr.....|N$.

...

Then for any $a,b,c$ where $c|ab$ we have $c|ab = a\frac{b}{\gcd(b,c)}\gcd(b,c)$ and therefore $c|a\gcd(b,c)$ (because $\frac{b}{\gcd(b,c)}$ and $c$ are coprime). Always.

$c|ab \iff c|a\gcd(b,c)$ is always true.

And if $\gcd(b,c) = 1$ then $c|ab \iff c|a$.

=====

Let $c = \prod p_i^{k_i}$ be the prime factorization of $c$.

Then $c|ab$. But $\gcd(c,b) = 1$ so none of the prime factors of $c$ divide $b$. So they only divide $a$. so $c=\prod p_i^{k_i}|a$.

Answer 2

You can start with Bezout's Identity:

$cx + by = 1$ for some $x,y \in \mathbb{Z}$

Then you multiply by $a$: $$acx + aby = a$$ Then you have $c|ac$ and $c|ab$ (hypothesis), so: $$c | (acx+aby) = a \Rightarrow c|a$$

Answer 3

Prove by induction. If $c=1$, $a$ must be divisable by $c$. If $c>1$, let $p$ be its prime divisor. Since $ab$ is divisable by $c$ and $c$ is divisable by $p$, $ab$ is divisable by $p$. But $b$ is not divisable by $p$, otherwise $p$ would be a common divisor of $b$ and $c$. Therefore $a$ is divisable by $p$. Let $a=pa'$, $c=pc'$, then $a'b/c' = ab/c$, so $a'b$ is divisable by $c'$. Since $gcd(b,c)=1$ and $c'$ is a divisor of $c$, $gcd(b, c')=1$. Therefore, $a'$ is divisable by $c'$. Since $a/c = a'/c'$, $a$ is divasable by $c$.