# Proofs about divisibility that seem obvious but eludes me

I'm very new to elementary number theory proofs and have been trying to figure out how to prove these seemingly straightforward identities with divisibility with no success.

For some integers $a,b,c \in \mathbb{Z}$

1) If ${a\mid bc}$ and ${a \not\mid b}$ then ${a\mid c}$

2) If ${a\mid c}$, ${b\mid c}$ and ${\gcd(a,b) = 1}$ then ${ab\mid c}$

For 1), example, if 2 divides 3a, then 2 clearly divides a because 2 does not divide 3... not sure how to formalize
For 2), I think it is somewhat related to the divisibility rule (https://en.wikipedia.org/wiki/Divisibility_rule). Let's say $6\mid 12$ and $3\mid 12$ is true but ${6\cdot 3\mid 12}$ is not and that relates to the fact that 6 is a multiple of 3. However, suppose ${2\mid a}$ and ${3\mid a}$. 2 and 3 are not multiples of each other and so the smallest number that is divisible by 2 and 3 must be a multiple of 2 and 3 (6 being the smallest), hence ${a}$ is divisible by 6. Is there a way to formalize this a better way?

The first claim is false: $4$ divides $(2\cdot 6)$ and $4$ does not divide $2$, do not imply that $4$ divides $6$.

For the second one, recall that if $\gcd(a,b)=1$ then, by the Bezout's identity, there are integers $m$ and $n$ such that $am+bn=1$. Moreover, $c=ra=sb$ for some integers $r$ and $s$. Hence $$c=c(am+bn)=cam+cbn=sbam+rabn=(ab)(sm+rn).$$

• I was going to respond to your hint but it seems like you gave the full answer for 2). Thanks! – CloudIcarus Oct 10 '17 at 8:10
• @CloudIcarus Well done. I edit my answer with the full solution so you can check your work. – Robert Z Oct 10 '17 at 8:13

1) As pointed by Robert, your claim is false. You should replace it by this statement:

If ${a|bc}$ and $gcd(a,b)=1$ then ${a|c}$

2) You have the right intuition.

Hint:

You can write the prime factorization of $a$,$b$ and $c$...

• I looked at your replacement statement but still not able to show how it is true. That said, I think it seems similar to the statement " if ${a|bc}$ then ${a|b}$ or ${a|c}$ " which I have a hunch about but not sure either. – CloudIcarus Oct 10 '17 at 8:43
• Oh, wait. Just got it. By Bezout's Theorem, ${ax + by = 1}$ for some ${x, y \in \mathbb{Z} }$, then ${cax + cby = c}$. Since we know ${bc = ap}$ for some ${p \in \mathbb{Z} }$, then ${cax + (bc)y = cax + apy = a(cx + py) = c}$. Hence ${a|c}$ – CloudIcarus Oct 10 '17 at 9:04