Let $a\mid c$ and $b\mid c$ such that greatest common divisor (gcd) $\gcd(a,b)=1$, Show that $ab\mid c$.
Let $a\mid c$ and $b\mid c$ such that $\gcd(a,b)=1$, Show that $ab\mid c$
3 Answers
HINT $\rm\quad\ \ a,b\ |\ c\ \Rightarrow\ ab\ |\ ac,bc\ \Rightarrow\ ab\ |\ (ac,bc) = (a,b)\:c = c\ $ via $\rm\:(a,b)= 1\:.$
NOTE $\ $ This proof works in every domain where GCDs exist, since it doesn't use Bezout's identity. Instead it uses the GCD distributive law $\rm\ (ac,bc) = (a,b)\:c\:,\ $ true in every GCD domain, viz.
LEMMA $\rm\quad (a,b)\ =\ (ac,bc)/c\ \ $ if $\rm\ (ac,bc)\ $ exists.
Proof $\rm\quad\ d\ |\ a,b\ \iff\ dc\ |\ ac,bc\ \iff\ dc\ |\ (ac,bc)\ \iff\ d\ |\ (ac,bc)/c$
The above proofs use the universal definitions of GCD, LCM, which often serve to simplify proofs, e.g. see this proof of the GCD * LCM law.
If $\operatorname{gcd}(a,b)=1$ then there exist $x,y$ such that $ax+by=1$. Now let $a,b|c$ and note that $c = cax+cby$. Can you show that both terms on the right hand side are divisible by $ab$?
-
0@alvoutila, you are right. :) – 2011-09-05
Here's a solution using set theory.
Let the set $A$ be the prime factors of $a$,
set $B$ be the set of prime factors of $b$,
and set $C$ be the prime factors of $c$.
- $a\;|\;c\Longrightarrow A\subset C$
- $b\;|\;c\Longrightarrow B\subset C$
- $\gcd(a,b) = 1 \Longrightarrow A\cap B\subset \varnothing$
We want to show that $ab\;|\;c \Longrightarrow A \cup B \subseteq C$.
Do you see why this is given the $3$ points above?