# Prove: If $a|m$ and $b|m$ and $\gcd(a,b)=1$ then $ab|m$

I think that $m=ab$ but I'm not sure exactly how to prove it or even if that's a correct conclusion. New to this divisibility/gcd stuff. Thanks in advance!

-
Hint: Bézout's identity. –  wj32 Sep 12 '12 at 23:22
No, you can’t conclude that $ab=m$: consider the example $a=2,b=3$, and $m=12$. –  Brian M. Scott Sep 12 '12 at 23:22
Oh ok. So all I really know is m=ax and m=by for some x,y $\in \mathbb{Z}$. Also, a and b are relatively prime since (a,b)=1. And @wj32 says to use aq+br=1 for some q,r $\in$\mathbb{Z}$. Any more hints? – user39794 Sep 12 '12 at 23:27 @AllisonCameron Big spoiler: multiply both sides by$m$, and do some substitutions. – wj32 Sep 12 '12 at 23:31 @wj32 Ok so tell me if I'm on the right track... maq+mbr=m so byaq+axbr=m. So since there is an ab in each term, ab can divide m? AHH I get it now I think. It was so simple! Thank you! – user39794 Sep 12 '12 at 23:54 add comment ## 5 Answers Write$ax+by=1$,$m=aa'$,$m=bb'$. Let$t=b'x+a'y$. Then$abt=abb'x+baa'y=m(ax+by)=m$and so$ab \mid m$. Edit: Perhaps this order is more natural and less magical:$m = m(ax+by) = max+mby = bb'ax+aa'by = ab(b'x+a'y)$. - This is exactly what ended up working (at least at a level I could understand). Thanks for the help! – user39794 Sep 13 '12 at 0:01 really nice answer – user4140 Sep 13 '12 at 0:20 add comment Hint$\rm\quad \begin{eqnarray}\rm b\:|\:m\ \Rightarrow\ ab\:|\:am\\ \rm a\:|\:m\ \Rightarrow\ ab\:|\:bm\end{eqnarray}\ \ \Rightarrow\ ab\:|\:(am,bm)\, =\, (a,b)m\, =\, m\ \ $by$\rm\ \ (a,b) = 1.$Remark$\ $If above one employs the linear representation of the gcd (Bezout's Identity), replacing$\rm\:(a,b)\:$by$\rm\:ax + by,\:$then one obtains essentially the proof in lhf's answer. The above proof is more general since there are rings with gcds not of linear (Bezout) form. Further, the above presentation highlights the key role played by the distributive law for gcds, i.e.$\rm\:(a,b)\,c = (ac,bc).$A similar proof yields the generalization$\rm\ gcd(a,b)\,lcm(a,b)\, =\, ab,\ \ $the gcd$*$lcm law, which yields the sought equality for the special case$\rm\:gcd(a,b) = 1.$- add comment If$\gcd (a,b) =1$, then$a$and$b$have no prime factors in common. This means if we divide$m$by$a$, the result is still divisible by$b$. So$b | \frac{m}{a}$, thus$ab|m$. - We know that$a|m$from the statement of the problem. I am saying that when we divide$m$by$a$, we get another integer that is a product of primes. Since$a$and$b$have no primes in common,$b$will still divide this new integer. Thus$ab|m$. – Tarnation Sep 12 '12 at 23:33 It may be, however, that Allison’s course hasn’t yet reached unique factorization, in which case this argument is unusable. – Brian M. Scott Sep 12 '12 at 23:37 add comment HINT: You know that there is an integer$k$such that$ak=m$. Now you have$b\mid ak$and$(a,b)=1$; do you know a theorem that let’s you draw a conclusion about$b$and$k$? (The theorem that I have in mind can be proved using Bézout’s lemma; the argument is the one that wj32 has in mind for your question, but it’s not necessary if you already know this theorem.) - add comment Ok first of all let me show you that m does not equal ab necessarily. suppose m=36. a=2 and$b=3$.$ab=6$and a|b and a|b. Now lets go to the other part of the problem. lets put a in prime factorization.$a=2^{a_2}*3^{a_3}...p^{a_p}$and$b=2^{b_2}*3^{b_3}...p^{b_p}$where p is a prime number.So then$\gcd(a,b)= 1$if and only if$(a_i+b_i)=max(a_i,b_i)$for any prime i. Now lets do the same prime decomposition for m.$m=2^{m_2}*3^{m_3}...p^{m_p}$so then a can only divide m if$a_i\leq m_i$for any prime i. also$a*b=2^{a_2+b_2}*3^{a_3+b_3}...p^{a_p+bp}$but since (a,b)=1 this is equal to$2^{max(a_i,b_i)}*3^{max(a_i,b_i)}...*p^{max(a_p*b_p)}$and since$m_i>a_i $and$m_i>b_i $then$m_i>max(a_i,b_i)\$ as desired

-
I would appreciate it if the people who downvoted my answer explained why. –  user4140 Sep 13 '12 at 0:18