Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$?
share|improve this question

2 Answers 2

up vote 8 down vote accepted

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

share|improve this answer
    
This is too small for an edit (for technical reasons), but you have a typo in "Since $a|c$, we can write $c=ba$", which should read "...$c=ak$". –  Luke Mathieson Jul 21 '12 at 4:13
    
@Luke: Huh?${}{}{}$ –  Arturo Magidin Jul 21 '12 at 4:14
    
Hopefully that makes sense now, typing on a real keyboard makes things a wee bit easier and less error prone. –  Luke Mathieson Jul 21 '12 at 4:19
    
@Luke: Ah, gotcha. Yes, thank you. –  Arturo Magidin Jul 21 '12 at 4:20

$\rm\, a\:|\:c\:\Rightarrow\:ab\:|\:bc\:\Rightarrow\: \color{#0A0}{\bf a}\:|\:\color{blue}{\bf b}\,(c/b)\color{#C00}\Rightarrow\, a\:|\:c/b\:\Rightarrow\:ab\:|\:c\ \, $ by $\rm\,\ (\color{#0A0}{\bf a},\color{blue}{\bf b})=1\,$ and $\rm\color{#C00}{Euclid's\ Lemma}$

The converse is easy: $\rm\:a\:|\:ab\:|\:c\:\Rightarrow\: a\:|\:c\:$ by transitivity of "divides".

share|improve this answer
    
Drat! Arturo beat me to it. –  robjohn Jul 21 '12 at 3:16
2  
@Rob But you have bigger Bezouka's. Ready, aim, fire! –  Bill Dubuque Jul 21 '12 at 3:19

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.