5
$\begingroup$

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

I thought that $m=ab$ but I was given a counterexample in a comment below.

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 $\gcd(a,b)=1$.

One of the comments suggests to use Bézout's identity, i.e., $aq+br=1$ for some $q,r\in\mathbb{Z}$. Any more hints?

New to this divisibility/gcd stuff. Thanks in advance!

$\endgroup$
  • 1
    $\begingroup$ Hint: Bézout's identity. $\endgroup$ – wj32 Sep 12 '12 at 23:22
  • 3
    $\begingroup$ No, you can’t conclude that $ab=m$: consider the example $a=2,b=3$, and $m=12$. $\endgroup$ – Brian M. Scott Sep 12 '12 at 23:22
  • $\begingroup$ 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? $\endgroup$ – user39794 Sep 12 '12 at 23:27
  • 1
    $\begingroup$ @AllisonCameron Big spoiler: multiply both sides by $m$, and do some substitutions. $\endgroup$ – wj32 Sep 12 '12 at 23:31
  • $\begingroup$ @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! $\endgroup$ – user39794 Sep 12 '12 at 23:54
7
$\begingroup$

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

$\endgroup$
  • $\begingroup$ This is exactly what ended up working (at least at a level I could understand). Thanks for the help! $\endgroup$ – user39794 Sep 13 '12 at 0:01
  • $\begingroup$ really nice answer $\endgroup$ – Jorge Fernández Hidalgo Sep 13 '12 at 0:20
6
$\begingroup$

Hint $\rm\qquad a,b\mid m\iff ab\mid am,bm \iff ab\mid \overbrace{(am,bm)}^{\large \color{#c00}{ (a,\,b)\,m}}\iff ab/(a,b)\mid m$

Remark $\ $ If above we employ Bezout's Identity to replace the gcd $\rm\:(a,b)\:$ by $\rm\:j\,a + k\,b\:$ (its linear representation) then we obtain the proof by Bezout in lhf's answer (but using divisibility language). Note the key role played by the gcd distributive law, i.e. $\rm\:\color{#c00}{(a,b)\,c} = (ac,bc).$

This proof is more general than the Bezout proof since there are rings with gcds not of linear (Bezout) form, e.g. $\rm \Bbb Z[x,y]$ the ring of polynomials in $\,\rm x,y\,$ with integer coefficients, where $\,\rm gcd(x,y) = 1\,$ but $\rm\, x\, f + y\, g\neq 1\,$ (else evaluating at $\rm\,x,y = 0\,$ yields $\,0 = 1).\,$

The proof shows that $\rm\ a,b\mid m\iff ab/(a,b)\mid m,\ $ i.e. $\ \rm lcm(a,b) = ab/(a,b)\ $ using the universal definition of lcm. $ $ The OP is the special case $\rm\,(a,b)= 1.$

$\endgroup$
  • $\begingroup$ See here for a proof by cofactor duality. $\endgroup$ – Bill Dubuque Dec 6 '18 at 20:45
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Tarnation Sep 12 '12 at 23:33
  • 1
    $\begingroup$ It may be, however, that Allison’s course hasn’t yet reached unique factorization, in which case this argument is unusable. $\endgroup$ – Brian M. Scott Sep 12 '12 at 23:37
1
$\begingroup$

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|m and b|m. 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

$\endgroup$
  • $\begingroup$ I would appreciate it if the people who downvoted my answer explained why. $\endgroup$ – Jorge Fernández Hidalgo Sep 13 '12 at 0:18
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy