Given two numbers $a$ and $b$, where $a$ is co-prime to $b$,
- Show that for any number $c$, if $a|c$ and $b | c$ then $ab| c$.
- Is the reverse also true? In other words, if $ab |c$ and $a$ is co-prime to $b$, then do we have $a | c$ as well as $b|c$?
Answer
The second property holds, but the assumption that $\gcd(a,b)=1$ is superfluous. In general, if $x|y$ and $y|z$, then $x|z$. Since $a|ab$ and $b|ab$, then $ab|c$ implies $a|c$ and $b|c$, without any conditions on $\gcd(a,b)$.
On the other hand, $\gcd(a,b)=1$ is required for the first.
There are a number of ways of doing the proof. One is to use the Bezout identity: for any integers $a$ and $b$, there exist integers $x$ and $y$ such that $\gcd(a,b)=ax+by$. If $\gcd(a,b)=1$, then we can write $1 = ax+by$. Multiplying through by $c$, we get $c=axc + byc$. Since $a|c$, we can write $c=ak$; and since $b|c$, we can write $c=b\ell$. So we have
$$c = axc+byc = ax(b\ell) + by(ak) = ab(x\ell + yk),$$
so $ab|c$.
Another is to use the following property:
Lemma. If $a|xy$ and $\gcd(a,x)=1$, then $a|y$.
This can be done using the Bezout identity, but here is a proof that avoids it and only uses the properties of the gcd (so it is valid in a larger class of rings than Bezout rings):
$$\begin{align*}
r|\gcd(a,xy) & \iff
r|a,xy\\
&\iff r|ay, xy,a\\
&\iff r|\gcd(ay,xy),a\\
&\iff r|y\gcd(a,x),a\\
&\iff r|y,a\\
&\iff r|\gcd(a,y)
\end{align*}$$
In particular, $a=\gcd(a,xy)$ divides $\gcd(a,y)$, which divides $y$, hence $a|y$.
With that Lemma on hand, we obtain that the result you want as follows: If $a|c$, then $c=ak$ for some $k$. Then $b|ak$, $\gcd(a,b)=1$. so $b|k$. Hence $k=b\ell$; thus, $c=ak=ab\ell$, so $ab|c$.
No comments:
Post a Comment