If $a$ divides $bc$ and $\gcd(a,b) = d$ then $\frac a d$ divides c I'm trying to prove that if $a$ divides $bc$ and $\gcd(a,b) = d$ then $\frac a d$ divides c. I tried using Bezout identity but couldn't get anywhere. 
 A: Let $a=a'd$  and $b=b'd$. Note that $a'$ and $b'$ are relatively prime. We want to show that $a'$ divides $c$. Since $a'd$ divides $b'dc$, it follows that $a'$ divides $b'c$.
By the Bezout Identity there are integers $x$ and $y$ such that $a'x+b'y=1$. Multiply through by $c$. Note that $a'$ divides $a'xc$ and $a'$ divides $b'cy$. The result follows. 
A: $a\mid ac,bc\,\Rightarrow\, a\mid(ac,bc)\overset{\rm\color{#C00}{DL}}=(a,b)c\,\Rightarrow\,a/(a,b)\mid c\ $ by the GCD Distributive Law ($\rm\color{#C00}{DL}$)
A: I assume $ a, b, c, d \in \mathbb{Z} \setminus \{ 0 \} $. This question is then a duplicate of this. Here is an answer taken from that thread: 

If $a\mid bc$ and $(a,b)=1$ then $a\mid c$. Use this to show:
$$ \displaystyle  a \mid bc \implies \frac{a}{\gcd(a,b)} \mid
> \frac{b}{\gcd(a,b)}\times c \implies \frac{a}{\gcd(a,b)}\mid c $$
  Because $\gcd\left(\frac{a}{\gcd(a,b)},\frac{b}{\gcd(a,b)}\right)=1$.

A: This one is straightforward just using the algebraic properties of divisibility. Of particular note is that
$$ xz \mid yz \implies x \mid y $$
$$ \gcd(xz, yz) = gz \implies \gcd(x,y)=g $$
In fact, if you extend these definitions appropriately to rational numbers ("dividing" means the quotient is an integer), then
$$ x \mid y \implies \frac{x}{z} \mid \frac{y}{z} $$
$$ \gcd(x,y) = g \implies \gcd\left( \frac{x}{z}, \frac{y}{z} \right) = \frac{g}{z} $$
A: Let $\text{Factors}(x)$ be the multiset of prime factors of $x$.
Let $A = \text{Factors}(a)$, $B = \text{Factors}(b)$, $C = \text{Factors}(c)$, $D = \text{Factors}(d)$.  Translate expression appropriately:
$$\begin{array} {c|c}
a\mid bc & A \subseteq (B \cup C) \\
\text{gcd}(ab) = d & (A \cap B) = D \\
{a \over d} \mid c & (A - D) \subseteq C
\end{array}$$
The expression becomes $A \subseteq (B \cup C) \text{ and } (A \cap B) = D \quad \Rightarrow\quad (A - D) \subseteq C$
Let $\bar{a}$ be $x \in A$, etc, translate to boolean:
$\left(\bar{a} \Rightarrow (\bar{b} \text{ or } \bar{c})\right) \text{ and } \left((\bar{a} \text{ and } \bar{b}) \text{ xnor } \bar{d}\right) \quad \Rightarrow\quad \left((\bar{a} \text{ and not } \bar{b}) \Rightarrow \bar{c}\right)$
which can be checked by truth table or demorgans or whatever coNP combinatorial technique you prefer.
