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












2












$begingroup$


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!






elementary-number-theory







share|cite|improve this question











$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
















2












$begingroup$


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!






elementary-number-theory







share|cite|improve this question











$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














2












2








2


1



$begingroup$


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!






elementary-number-theory







share|cite|improve this question











$endgroup$




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!






elementary-number-theory




elementary-number-theory






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Sep 12 '12 at 23:48









M Turgeon

7,84133066




7,84133066










asked Sep 12 '12 at 23:19







user39794















  • 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














  • 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








1




1




$begingroup$
Hint: Bézout's identity.
$endgroup$
– wj32
Sep 12 '12 at 23:22




$begingroup$
Hint: Bézout's identity.
$endgroup$
– wj32
Sep 12 '12 at 23:22




3




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






$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




1




$begingroup$
@AllisonCameron Big spoiler: multiply both sides by $m$, and do some substitutions.
$endgroup$
– wj32
Sep 12 '12 at 23:31




$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




$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










5 Answers
5






active

oldest

votes


















5












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






share|cite|improve this answer











$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
    Sep 13 '12 at 0:20



















6












$begingroup$

Hint $rmqquad a,bmid miff abmid am,bm
iff abmid 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, gneq 1,$ (else evaluating at $rm,x,y = 0,$ yields $,0 = 1).,$



The proof shows that $rm a,bmid miff 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.$






share|cite|improve this answer











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






share|cite|improve this answer









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






share|cite|improve this answer











$endgroup$













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



















0












$begingroup$

HINT: You know that there is an integer $k$ such that $ak=m$. Now you have $bmid 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.)






share|cite|improve this answer









$endgroup$













    Your Answer





    StackExchange.ifUsing("editor", function () {
    return StackExchange.using("mathjaxEditing", function () {
    StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
    StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
    });
    });
    }, "mathjax-editing");

    StackExchange.ready(function() {
    var channelOptions = {
    tags: "".split(" "),
    id: "69"
    };
    initTagRenderer("".split(" "), "".split(" "), channelOptions);

    StackExchange.using("externalEditor", function() {
    // Have to fire editor after snippets, if snippets enabled
    if (StackExchange.settings.snippets.snippetsEnabled) {
    StackExchange.using("snippets", function() {
    createEditor();
    });
    }
    else {
    createEditor();
    }
    });

    function createEditor() {
    StackExchange.prepareEditor({
    heartbeatType: 'answer',
    autoActivateHeartbeat: false,
    convertImagesToLinks: true,
    noModals: true,
    showLowRepImageUploadWarning: true,
    reputationToPostImages: 10,
    bindNavPrevention: true,
    postfix: "",
    imageUploader: {
    brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
    contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
    allowUrls: true
    },
    noCode: true, onDemand: true,
    discardSelector: ".discard-answer"
    ,immediatelyShowMarkdownHelp:true
    });


    }
    });














    draft saved

    draft discarded


















    StackExchange.ready(
    function () {
    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f194961%2fprove-if-am-and-bm-and-gcda-b-1-then-abm%23new-answer', 'question_page');
    }
    );

    Post as a guest















    Required, but never shown
























    5 Answers
    5






    active

    oldest

    votes








    5 Answers
    5






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes









    5












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






    share|cite|improve this answer











    $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
      Sep 13 '12 at 0:20
















    5












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






    share|cite|improve this answer











    $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
      Sep 13 '12 at 0:20














    5












    5








    5





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






    share|cite|improve this answer











    $endgroup$



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







    share|cite|improve this answer














    share|cite|improve this answer



    share|cite|improve this answer








    edited Sep 13 '12 at 0:18

























    answered Sep 12 '12 at 23:53









    lhflhf

    164k10170395




    164k10170395












    • $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
      Sep 13 '12 at 0:20


















    • $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
      Sep 13 '12 at 0:20
















    $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$
    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
    Sep 13 '12 at 0:20




    $begingroup$
    really nice answer
    $endgroup$
    – Jorge Fernández
    Sep 13 '12 at 0:20











    6












    $begingroup$

    Hint $rmqquad a,bmid miff abmid am,bm
    iff abmid 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, gneq 1,$ (else evaluating at $rm,x,y = 0,$ yields $,0 = 1).,$



    The proof shows that $rm a,bmid miff 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.$






    share|cite|improve this answer











    $endgroup$













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
















    6












    $begingroup$

    Hint $rmqquad a,bmid miff abmid am,bm
    iff abmid 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, gneq 1,$ (else evaluating at $rm,x,y = 0,$ yields $,0 = 1).,$



    The proof shows that $rm a,bmid miff 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.$






    share|cite|improve this answer











    $endgroup$













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














    6












    6








    6





    $begingroup$

    Hint $rmqquad a,bmid miff abmid am,bm
    iff abmid 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, gneq 1,$ (else evaluating at $rm,x,y = 0,$ yields $,0 = 1).,$



    The proof shows that $rm a,bmid miff 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.$






    share|cite|improve this answer











    $endgroup$



    Hint $rmqquad a,bmid miff abmid am,bm
    iff abmid 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, gneq 1,$ (else evaluating at $rm,x,y = 0,$ yields $,0 = 1).,$



    The proof shows that $rm a,bmid miff 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.$







    share|cite|improve this answer














    share|cite|improve this answer



    share|cite|improve this answer








    edited Oct 12 '18 at 23:13

























    answered Sep 12 '12 at 23:57









    Bill DubuqueBill Dubuque

    210k29191639




    210k29191639












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


















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
















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




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






    share|cite|improve this answer









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

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






    share|cite|improve this answer









    $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












    1








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






    share|cite|improve this answer









    $endgroup$



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







    share|cite|improve this answer












    share|cite|improve this answer



    share|cite|improve this answer










    answered Sep 12 '12 at 23:24









    TarnationTarnation

    1,111714




    1,111714












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


















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
















    $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




    $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




    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




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






    share|cite|improve this answer











    $endgroup$













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
















    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_ileq 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






    share|cite|improve this answer











    $endgroup$













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














    1












    1








    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_ileq 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






    share|cite|improve this answer











    $endgroup$



    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_ileq 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







    share|cite|improve this answer














    share|cite|improve this answer



    share|cite|improve this answer








    edited Jun 2 '14 at 1:53

























    answered Sep 12 '12 at 23:40









    Jorge FernándezJorge Fernández

    75.3k1190192




    75.3k1190192












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


















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
















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




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











    0












    $begingroup$

    HINT: You know that there is an integer $k$ such that $ak=m$. Now you have $bmid 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.)






    share|cite|improve this answer









    $endgroup$


















      0












      $begingroup$

      HINT: You know that there is an integer $k$ such that $ak=m$. Now you have $bmid 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.)






      share|cite|improve this answer









      $endgroup$
















        0












        0








        0





        $begingroup$

        HINT: You know that there is an integer $k$ such that $ak=m$. Now you have $bmid 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.)






        share|cite|improve this answer









        $endgroup$



        HINT: You know that there is an integer $k$ such that $ak=m$. Now you have $bmid 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.)







        share|cite|improve this answer












        share|cite|improve this answer



        share|cite|improve this answer










        answered Sep 12 '12 at 23:32









        Brian M. ScottBrian M. Scott

        456k38509909




        456k38509909






























            draft saved

            draft discarded




















































            Thanks for contributing an answer to Mathematics Stack Exchange!


            • Please be sure to answer the question. Provide details and share your research!

            But avoid …



            • Asking for help, clarification, or responding to other answers.

            • Making statements based on opinion; back them up with references or personal experience.


            Use MathJax to format equations. MathJax reference.


            To learn more, see our tips on writing great answers.




            draft saved


            draft discarded














            StackExchange.ready(
            function () {
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f194961%2fprove-if-am-and-bm-and-gcda-b-1-then-abm%23new-answer', 'question_page');
            }
            );

            Post as a guest















            Required, but never shown





















































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown

































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown







            -

            Popular posts from this blog

            Probability when a professor distributes a quiz and homework assignment to a class of n students.

            Image
            0 0 $begingroup$ Need help with this problem. Suppose our lazy professor collects a quiz and a homework assignment from a class of n students one day, then distributes both the quizzes and the homework assignments back to the class in a random fashion for grading. Each student receives one quiz and one homework assignment to grade. (a) What is the probability that every student receives someone else's quiz to grade, and someone else's homework to grade? (b) What is the probability that no student receives both their own quiz and their own homework assignment to grade? In this case, some students may receive their own quiz, and others may receive their own homework assignment. (c) Compute the limiting probability as n approaches infinity in each case. ...
            Read more

            Aardman Animations

            Image
            Aardman Animations, Ltd. Aardman Animations Tipo privada Atividade Animação em stop-motion , Animação em CGI Fundação 1972 Fundador(es) Peter Lord David Sproxton Sede Bristol, Inglaterra  Reino Unido Proprietário(s) Dreamworks Pessoas-chave Peter Lord David Sproxton Nick Park Divisões Aardman Features Aardman Digital Aardman Commercials Aardman Broadcast Aardman International Aardman Rights Aardman Effects Aardman 3-D Systems Aardman Nathan Love AardBoiled Website oficial aardman.com ...
            Read more

            Are they similar matrix

            Image
            0 $begingroup$ Do $begin{bmatrix} 0&i&0\0&0&1\0&0&0 end{bmatrix} $ and $begin{bmatrix} 0&0&0\-i&0&0\0&1&0 end{bmatrix} $ are similar.Is this True/false Clearly both are nilpotent and one is conjucate transpose of other but how to know if they are similar.i'm stuck. Please help me linear-algebra vector-spaces eigenvalues-eigenvectors generalizedeigenvector share | cite | improve this question edited Dec 10 '18 at 6:38 Vasanth Kris asked Dec 10 '18 at 6:19 ...
            Read more