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

5 Answers 5

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$
2
  • $\begingroup$ This is exactly what ended up working (at least at a level I could understand). Thanks for the help! $\endgroup$
    – user39794
    Sep 13, 2012 at 0:01
  • $\begingroup$ really nice answer $\endgroup$
    – Asinomás
    Sep 13, 2012 at 0:20
6
$\begingroup$

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

Remark $\ $ We used $\rm\color{#0a0} U$= gcd Universal Property and the gcd distributive law $\rm\:\color{#c00}{(a,b)\,c} = (ac,bc).\ $ 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).

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$
1
  • $\begingroup$ See here for a proof by cofactor duality. $\endgroup$ Dec 6, 2018 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$
2
  • $\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, 2012 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$ Sep 12, 2012 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$
1
  • $\begingroup$ I would appreciate it if the people who downvoted my answer explained why. $\endgroup$
    – Asinomás
    Sep 13, 2012 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