Proofs about divisibility that seem obvious but eludes me

106 Views Asked by At

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?

2

There are 2 best solutions below

2
On BEST ANSWER

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).$$

2
On

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$...