Prove that if $a\mid bc$ and $\gcd(a,b)=1$, then $a\mid c$ without Bezout

Question

If $a\mid bc$ and $\gcd(a,b)=1$, prove that $a\mid c$ without using Bezout's Identity.

Answer 1

First, show by strong induction that every integer greater than $1$ has a prime factorization. If $a | bc$ and $\gcd(a,b)=1,$ then $bc = ka,k\in\mathbb{Z}$ and $a$ and $b$ do not have any prime factors in common. Since $bc=ka,$ $k$ must contain all the prime factors to powers equal to those of $b$ (this applies even if $b$ has no prime factors), so $\frac{ka}{b} = c$ must be an integer. Since this is an integer multiple of $a,$ by definition $c | a.$

Answer 2

Denote $\mathrm{gcd}(a,b) =: (a,b)$. Then $a\mid bc$ and $a\mid ac$ implies $a\mid (ac,bc)$ i.e $a\mid c(a,b)$.

Answer 3

Do strong induction on $b$. The case $b=1$ is obvious.

Suppose the statement holds for all numbers less than $b>1$. Take $p$ a prime divisor of $b$ and write $b=px$. Then $a\mid x(pc)$, so $a\mid pc$ by the induction hypothesis. In particular $pc=ay$ and, by Euclid’s theorem, either $p\mid a$ or $p\mid y$. The former case would imply $p\mid\gcd(a,b)$: contradiction. Hence $p\mid y$, $y=pz$ and $pc=apz$, so $a\mid c$.

---

The proof above uses (1) every integer $>1$ is divisible by at least a prime; (2) Euclids’s theorem if $p\mid xy$, for prime $p$, then either $p\mid x$ or $p\mid y$.

From these two facts one can deduce unique factorization into primes. Conversely, uniqueness of factorization into primes implies both (1) and (2) above.

On the other hand, the statement under scrutiny implies Euclid’s theorem. Assume it and suppose $p$ is a prime and $p\mid xy$. If $p\nmid x$, then $\gcd(p,x)=1$, so $p\mid y$ by assumption.

Here $\gcd(A,B)=1$ can be considered as a shorthand for “no prime divides both $A$ and $B$”, we don't actually need existence of the gcd in all the arguments above.