Show $aBbb Z+bBbb Z = gcd(a,b)Bbb Z$












1












$begingroup$


I have the following problem:



Let $a, b inmathbb{Z}$. Show that $,{ ax + by : x, y in mathbb{Z}} = { n gcd(a,b) : nin mathbb{Z} }$



I understand that the Bezout's lemma says that $gcd(a,b) = ax +by$, so Im not really how you would go about proving the above, it doesn't really make sense to me. Any help is appreciated1










share|cite|improve this question











$endgroup$












  • $begingroup$
    do you have any other conditions on $x$ and $y$ ?
    $endgroup$
    – wanderer
    Mar 19 '14 at 4:11










  • $begingroup$
    nope, theyre just integers
    $endgroup$
    – Alex Chavez
    Mar 19 '14 at 4:15










  • $begingroup$
    This is closely related to Proof of Extended Euclidean Algorithm?
    $endgroup$
    – robjohn
    Apr 4 '15 at 14:08
















1












$begingroup$


I have the following problem:



Let $a, b inmathbb{Z}$. Show that $,{ ax + by : x, y in mathbb{Z}} = { n gcd(a,b) : nin mathbb{Z} }$



I understand that the Bezout's lemma says that $gcd(a,b) = ax +by$, so Im not really how you would go about proving the above, it doesn't really make sense to me. Any help is appreciated1










share|cite|improve this question











$endgroup$












  • $begingroup$
    do you have any other conditions on $x$ and $y$ ?
    $endgroup$
    – wanderer
    Mar 19 '14 at 4:11










  • $begingroup$
    nope, theyre just integers
    $endgroup$
    – Alex Chavez
    Mar 19 '14 at 4:15










  • $begingroup$
    This is closely related to Proof of Extended Euclidean Algorithm?
    $endgroup$
    – robjohn
    Apr 4 '15 at 14:08














1












1








1


0



$begingroup$


I have the following problem:



Let $a, b inmathbb{Z}$. Show that $,{ ax + by : x, y in mathbb{Z}} = { n gcd(a,b) : nin mathbb{Z} }$



I understand that the Bezout's lemma says that $gcd(a,b) = ax +by$, so Im not really how you would go about proving the above, it doesn't really make sense to me. Any help is appreciated1










share|cite|improve this question











$endgroup$




I have the following problem:



Let $a, b inmathbb{Z}$. Show that $,{ ax + by : x, y in mathbb{Z}} = { n gcd(a,b) : nin mathbb{Z} }$



I understand that the Bezout's lemma says that $gcd(a,b) = ax +by$, so Im not really how you would go about proving the above, it doesn't really make sense to me. Any help is appreciated1







elementary-number-theory proof-writing divisibility






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Jan 11 at 0:16









Bill Dubuque

210k29192641




210k29192641










asked Mar 19 '14 at 3:58









Alex ChavezAlex Chavez

438720




438720












  • $begingroup$
    do you have any other conditions on $x$ and $y$ ?
    $endgroup$
    – wanderer
    Mar 19 '14 at 4:11










  • $begingroup$
    nope, theyre just integers
    $endgroup$
    – Alex Chavez
    Mar 19 '14 at 4:15










  • $begingroup$
    This is closely related to Proof of Extended Euclidean Algorithm?
    $endgroup$
    – robjohn
    Apr 4 '15 at 14:08


















  • $begingroup$
    do you have any other conditions on $x$ and $y$ ?
    $endgroup$
    – wanderer
    Mar 19 '14 at 4:11










  • $begingroup$
    nope, theyre just integers
    $endgroup$
    – Alex Chavez
    Mar 19 '14 at 4:15










  • $begingroup$
    This is closely related to Proof of Extended Euclidean Algorithm?
    $endgroup$
    – robjohn
    Apr 4 '15 at 14:08
















$begingroup$
do you have any other conditions on $x$ and $y$ ?
$endgroup$
– wanderer
Mar 19 '14 at 4:11




$begingroup$
do you have any other conditions on $x$ and $y$ ?
$endgroup$
– wanderer
Mar 19 '14 at 4:11












$begingroup$
nope, theyre just integers
$endgroup$
– Alex Chavez
Mar 19 '14 at 4:15




$begingroup$
nope, theyre just integers
$endgroup$
– Alex Chavez
Mar 19 '14 at 4:15












$begingroup$
This is closely related to Proof of Extended Euclidean Algorithm?
$endgroup$
– robjohn
Apr 4 '15 at 14:08




$begingroup$
This is closely related to Proof of Extended Euclidean Algorithm?
$endgroup$
– robjohn
Apr 4 '15 at 14:08










5 Answers
5






active

oldest

votes


















1












$begingroup$

By Bezout, $ ngcd(a,b) = n(aj+bk),$ $Rightarrow$ $,gcd(a,b),Bbb Zsubseteq aBbb Z+bBbb Z., $ Conversely,



$,gcd(a,b)mid a,b,Rightarrow,gcd(a,b)mid ax!+!by,,$ so $,ax!+!by = ngcd(a,b),,$ so $,a,Bbb Z+b,Bbb Zsubseteq gcd(a,b)Bbb Z$





Or we can induct. $ $ wlog $,a,b> 0,$ by $,-aBbb Z = aBbb Z,, (pm a,pm b) = (a,b),,$ and it is true if $,a,$ or $,b=0.$



Proof by induction on $,color{#90f}{{rm size} := a+b}.,$ True if $,a = b!: aBbb Z + aBbb Z = aBbb Z.,$ Else $,aneq b.,$ By symmetry, wlog $,a>b.,$ $,aBbb Z+bBbb Z = color{#0a0}{(a!-!b)Bbb Z+bBbb Z} = (a!-!b,b)Bbb Z = (a,b)Bbb Z,$ because the $,color{#0a0}{rm green},$ instance has smaller $,color{#90f}{{rm size}} = (a!-!b)+b = a < color{#90f}{a+b},,$ so $rmcolor{}{induction},$ applies. $ $ QED






share|cite|improve this answer











$endgroup$





















    2












    $begingroup$

    Bezout's lemma says that there is a solution for every pair of natural numbers $(a,b)$ to the linear Diophantine equation: $$gcd(a,b)=ax+by$$



    Now define $k=ax+by$



    And let $(x,y)$ run over the integers.



    We have $gcd(a,b)mid k$ because it divides the right hand side.



    Thus $k$ must be an integer multiple of $gcd(a,b)$.



    But by Bezout's lemma we know there is a solution $(x_0,y_0)=(nx,yx)$ to $$ngcd(a,b)=ax_0+by_0$$



    Thus we have shown all values of $k$ must be of the form $ngcd(a,b)$ and that for every $ngcd(a,b)$ with $nin mathbb{Z}$ there exists integers $(x_0,y_0)$ satisfying the linear equation. Which completes the proof.






    share|cite|improve this answer









    $endgroup$





















      1












      $begingroup$

      To prove equality of two sets, you need to show that each is contained in the other.



      ${ax+by | x,y in Bbb Z} subset {n gcd(a,b) | n in Bbb Z}$, because for a given element of the former $ax+by$, we can take $n=frac{a}{gcd(a,b)}x+frac{b}{gcd(a,b)}y$ to see that it is an element of the latter set.



      Now as you pointed out there exists a pair of integers $x,y$ such that $ax+by = gcd(a,b)$. Can you use this to show that ${n gcd(a,b) | n in Bbb Z} subset {ax+by | x,y in Bbb Z}$?






      share|cite|improve this answer









      $endgroup$





















        0












        $begingroup$

        Let $k = text{gcd}(a, b)$



        Then $ax + by = k(frac{a}{k} x + frac{b}{k} y)$



        Then since $x, y, frac{a}{k}, frac{b}{k}$ are all integers, so is the entire expression, which is $n$.






        share|cite|improve this answer









        $endgroup$





















          0












          $begingroup$

          Trivially $(a,b)mid ax+by$ (since $(a,b)mid a$ and $(a,b)mid b$).



          This shows ${ax+bymid x,yinmathbb Z}subseteq {n(a,b)mid ninmathbb Z}$.





          Now prove $exists x,yinmathbb Z$ such that $n(a,b)=ax+by$.$ (2)$



          Euclid's algorithm shows that $exists x_0,y_0inmathbb Z ((a,b)=ax_0+by_0)$. Use this to show $(2)$.



          This concludes that ${n(a,b)mid ninmathbb Z}subseteq{ax+bymid x,yinmathbb Z}$.






          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%2f717771%2fshow-a-bbb-zb-bbb-z-gcda-b-bbb-z%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









            1












            $begingroup$

            By Bezout, $ ngcd(a,b) = n(aj+bk),$ $Rightarrow$ $,gcd(a,b),Bbb Zsubseteq aBbb Z+bBbb Z., $ Conversely,



            $,gcd(a,b)mid a,b,Rightarrow,gcd(a,b)mid ax!+!by,,$ so $,ax!+!by = ngcd(a,b),,$ so $,a,Bbb Z+b,Bbb Zsubseteq gcd(a,b)Bbb Z$





            Or we can induct. $ $ wlog $,a,b> 0,$ by $,-aBbb Z = aBbb Z,, (pm a,pm b) = (a,b),,$ and it is true if $,a,$ or $,b=0.$



            Proof by induction on $,color{#90f}{{rm size} := a+b}.,$ True if $,a = b!: aBbb Z + aBbb Z = aBbb Z.,$ Else $,aneq b.,$ By symmetry, wlog $,a>b.,$ $,aBbb Z+bBbb Z = color{#0a0}{(a!-!b)Bbb Z+bBbb Z} = (a!-!b,b)Bbb Z = (a,b)Bbb Z,$ because the $,color{#0a0}{rm green},$ instance has smaller $,color{#90f}{{rm size}} = (a!-!b)+b = a < color{#90f}{a+b},,$ so $rmcolor{}{induction},$ applies. $ $ QED






            share|cite|improve this answer











            $endgroup$


















              1












              $begingroup$

              By Bezout, $ ngcd(a,b) = n(aj+bk),$ $Rightarrow$ $,gcd(a,b),Bbb Zsubseteq aBbb Z+bBbb Z., $ Conversely,



              $,gcd(a,b)mid a,b,Rightarrow,gcd(a,b)mid ax!+!by,,$ so $,ax!+!by = ngcd(a,b),,$ so $,a,Bbb Z+b,Bbb Zsubseteq gcd(a,b)Bbb Z$





              Or we can induct. $ $ wlog $,a,b> 0,$ by $,-aBbb Z = aBbb Z,, (pm a,pm b) = (a,b),,$ and it is true if $,a,$ or $,b=0.$



              Proof by induction on $,color{#90f}{{rm size} := a+b}.,$ True if $,a = b!: aBbb Z + aBbb Z = aBbb Z.,$ Else $,aneq b.,$ By symmetry, wlog $,a>b.,$ $,aBbb Z+bBbb Z = color{#0a0}{(a!-!b)Bbb Z+bBbb Z} = (a!-!b,b)Bbb Z = (a,b)Bbb Z,$ because the $,color{#0a0}{rm green},$ instance has smaller $,color{#90f}{{rm size}} = (a!-!b)+b = a < color{#90f}{a+b},,$ so $rmcolor{}{induction},$ applies. $ $ QED






              share|cite|improve this answer











              $endgroup$
















                1












                1








                1





                $begingroup$

                By Bezout, $ ngcd(a,b) = n(aj+bk),$ $Rightarrow$ $,gcd(a,b),Bbb Zsubseteq aBbb Z+bBbb Z., $ Conversely,



                $,gcd(a,b)mid a,b,Rightarrow,gcd(a,b)mid ax!+!by,,$ so $,ax!+!by = ngcd(a,b),,$ so $,a,Bbb Z+b,Bbb Zsubseteq gcd(a,b)Bbb Z$





                Or we can induct. $ $ wlog $,a,b> 0,$ by $,-aBbb Z = aBbb Z,, (pm a,pm b) = (a,b),,$ and it is true if $,a,$ or $,b=0.$



                Proof by induction on $,color{#90f}{{rm size} := a+b}.,$ True if $,a = b!: aBbb Z + aBbb Z = aBbb Z.,$ Else $,aneq b.,$ By symmetry, wlog $,a>b.,$ $,aBbb Z+bBbb Z = color{#0a0}{(a!-!b)Bbb Z+bBbb Z} = (a!-!b,b)Bbb Z = (a,b)Bbb Z,$ because the $,color{#0a0}{rm green},$ instance has smaller $,color{#90f}{{rm size}} = (a!-!b)+b = a < color{#90f}{a+b},,$ so $rmcolor{}{induction},$ applies. $ $ QED






                share|cite|improve this answer











                $endgroup$



                By Bezout, $ ngcd(a,b) = n(aj+bk),$ $Rightarrow$ $,gcd(a,b),Bbb Zsubseteq aBbb Z+bBbb Z., $ Conversely,



                $,gcd(a,b)mid a,b,Rightarrow,gcd(a,b)mid ax!+!by,,$ so $,ax!+!by = ngcd(a,b),,$ so $,a,Bbb Z+b,Bbb Zsubseteq gcd(a,b)Bbb Z$





                Or we can induct. $ $ wlog $,a,b> 0,$ by $,-aBbb Z = aBbb Z,, (pm a,pm b) = (a,b),,$ and it is true if $,a,$ or $,b=0.$



                Proof by induction on $,color{#90f}{{rm size} := a+b}.,$ True if $,a = b!: aBbb Z + aBbb Z = aBbb Z.,$ Else $,aneq b.,$ By symmetry, wlog $,a>b.,$ $,aBbb Z+bBbb Z = color{#0a0}{(a!-!b)Bbb Z+bBbb Z} = (a!-!b,b)Bbb Z = (a,b)Bbb Z,$ because the $,color{#0a0}{rm green},$ instance has smaller $,color{#90f}{{rm size}} = (a!-!b)+b = a < color{#90f}{a+b},,$ so $rmcolor{}{induction},$ applies. $ $ QED







                share|cite|improve this answer














                share|cite|improve this answer



                share|cite|improve this answer








                edited Apr 4 '15 at 21:57

























                answered Mar 19 '14 at 4:17









                Bill DubuqueBill Dubuque

                210k29192641




                210k29192641























                    2












                    $begingroup$

                    Bezout's lemma says that there is a solution for every pair of natural numbers $(a,b)$ to the linear Diophantine equation: $$gcd(a,b)=ax+by$$



                    Now define $k=ax+by$



                    And let $(x,y)$ run over the integers.



                    We have $gcd(a,b)mid k$ because it divides the right hand side.



                    Thus $k$ must be an integer multiple of $gcd(a,b)$.



                    But by Bezout's lemma we know there is a solution $(x_0,y_0)=(nx,yx)$ to $$ngcd(a,b)=ax_0+by_0$$



                    Thus we have shown all values of $k$ must be of the form $ngcd(a,b)$ and that for every $ngcd(a,b)$ with $nin mathbb{Z}$ there exists integers $(x_0,y_0)$ satisfying the linear equation. Which completes the proof.






                    share|cite|improve this answer









                    $endgroup$


















                      2












                      $begingroup$

                      Bezout's lemma says that there is a solution for every pair of natural numbers $(a,b)$ to the linear Diophantine equation: $$gcd(a,b)=ax+by$$



                      Now define $k=ax+by$



                      And let $(x,y)$ run over the integers.



                      We have $gcd(a,b)mid k$ because it divides the right hand side.



                      Thus $k$ must be an integer multiple of $gcd(a,b)$.



                      But by Bezout's lemma we know there is a solution $(x_0,y_0)=(nx,yx)$ to $$ngcd(a,b)=ax_0+by_0$$



                      Thus we have shown all values of $k$ must be of the form $ngcd(a,b)$ and that for every $ngcd(a,b)$ with $nin mathbb{Z}$ there exists integers $(x_0,y_0)$ satisfying the linear equation. Which completes the proof.






                      share|cite|improve this answer









                      $endgroup$
















                        2












                        2








                        2





                        $begingroup$

                        Bezout's lemma says that there is a solution for every pair of natural numbers $(a,b)$ to the linear Diophantine equation: $$gcd(a,b)=ax+by$$



                        Now define $k=ax+by$



                        And let $(x,y)$ run over the integers.



                        We have $gcd(a,b)mid k$ because it divides the right hand side.



                        Thus $k$ must be an integer multiple of $gcd(a,b)$.



                        But by Bezout's lemma we know there is a solution $(x_0,y_0)=(nx,yx)$ to $$ngcd(a,b)=ax_0+by_0$$



                        Thus we have shown all values of $k$ must be of the form $ngcd(a,b)$ and that for every $ngcd(a,b)$ with $nin mathbb{Z}$ there exists integers $(x_0,y_0)$ satisfying the linear equation. Which completes the proof.






                        share|cite|improve this answer









                        $endgroup$



                        Bezout's lemma says that there is a solution for every pair of natural numbers $(a,b)$ to the linear Diophantine equation: $$gcd(a,b)=ax+by$$



                        Now define $k=ax+by$



                        And let $(x,y)$ run over the integers.



                        We have $gcd(a,b)mid k$ because it divides the right hand side.



                        Thus $k$ must be an integer multiple of $gcd(a,b)$.



                        But by Bezout's lemma we know there is a solution $(x_0,y_0)=(nx,yx)$ to $$ngcd(a,b)=ax_0+by_0$$



                        Thus we have shown all values of $k$ must be of the form $ngcd(a,b)$ and that for every $ngcd(a,b)$ with $nin mathbb{Z}$ there exists integers $(x_0,y_0)$ satisfying the linear equation. Which completes the proof.







                        share|cite|improve this answer












                        share|cite|improve this answer



                        share|cite|improve this answer










                        answered Mar 19 '14 at 4:20









                        EthanEthan

                        6,85512164




                        6,85512164























                            1












                            $begingroup$

                            To prove equality of two sets, you need to show that each is contained in the other.



                            ${ax+by | x,y in Bbb Z} subset {n gcd(a,b) | n in Bbb Z}$, because for a given element of the former $ax+by$, we can take $n=frac{a}{gcd(a,b)}x+frac{b}{gcd(a,b)}y$ to see that it is an element of the latter set.



                            Now as you pointed out there exists a pair of integers $x,y$ such that $ax+by = gcd(a,b)$. Can you use this to show that ${n gcd(a,b) | n in Bbb Z} subset {ax+by | x,y in Bbb Z}$?






                            share|cite|improve this answer









                            $endgroup$


















                              1












                              $begingroup$

                              To prove equality of two sets, you need to show that each is contained in the other.



                              ${ax+by | x,y in Bbb Z} subset {n gcd(a,b) | n in Bbb Z}$, because for a given element of the former $ax+by$, we can take $n=frac{a}{gcd(a,b)}x+frac{b}{gcd(a,b)}y$ to see that it is an element of the latter set.



                              Now as you pointed out there exists a pair of integers $x,y$ such that $ax+by = gcd(a,b)$. Can you use this to show that ${n gcd(a,b) | n in Bbb Z} subset {ax+by | x,y in Bbb Z}$?






                              share|cite|improve this answer









                              $endgroup$
















                                1












                                1








                                1





                                $begingroup$

                                To prove equality of two sets, you need to show that each is contained in the other.



                                ${ax+by | x,y in Bbb Z} subset {n gcd(a,b) | n in Bbb Z}$, because for a given element of the former $ax+by$, we can take $n=frac{a}{gcd(a,b)}x+frac{b}{gcd(a,b)}y$ to see that it is an element of the latter set.



                                Now as you pointed out there exists a pair of integers $x,y$ such that $ax+by = gcd(a,b)$. Can you use this to show that ${n gcd(a,b) | n in Bbb Z} subset {ax+by | x,y in Bbb Z}$?






                                share|cite|improve this answer









                                $endgroup$



                                To prove equality of two sets, you need to show that each is contained in the other.



                                ${ax+by | x,y in Bbb Z} subset {n gcd(a,b) | n in Bbb Z}$, because for a given element of the former $ax+by$, we can take $n=frac{a}{gcd(a,b)}x+frac{b}{gcd(a,b)}y$ to see that it is an element of the latter set.



                                Now as you pointed out there exists a pair of integers $x,y$ such that $ax+by = gcd(a,b)$. Can you use this to show that ${n gcd(a,b) | n in Bbb Z} subset {ax+by | x,y in Bbb Z}$?







                                share|cite|improve this answer












                                share|cite|improve this answer



                                share|cite|improve this answer










                                answered Mar 19 '14 at 4:15









                                Mike MillerMike Miller

                                37.2k472139




                                37.2k472139























                                    0












                                    $begingroup$

                                    Let $k = text{gcd}(a, b)$



                                    Then $ax + by = k(frac{a}{k} x + frac{b}{k} y)$



                                    Then since $x, y, frac{a}{k}, frac{b}{k}$ are all integers, so is the entire expression, which is $n$.






                                    share|cite|improve this answer









                                    $endgroup$


















                                      0












                                      $begingroup$

                                      Let $k = text{gcd}(a, b)$



                                      Then $ax + by = k(frac{a}{k} x + frac{b}{k} y)$



                                      Then since $x, y, frac{a}{k}, frac{b}{k}$ are all integers, so is the entire expression, which is $n$.






                                      share|cite|improve this answer









                                      $endgroup$
















                                        0












                                        0








                                        0





                                        $begingroup$

                                        Let $k = text{gcd}(a, b)$



                                        Then $ax + by = k(frac{a}{k} x + frac{b}{k} y)$



                                        Then since $x, y, frac{a}{k}, frac{b}{k}$ are all integers, so is the entire expression, which is $n$.






                                        share|cite|improve this answer









                                        $endgroup$



                                        Let $k = text{gcd}(a, b)$



                                        Then $ax + by = k(frac{a}{k} x + frac{b}{k} y)$



                                        Then since $x, y, frac{a}{k}, frac{b}{k}$ are all integers, so is the entire expression, which is $n$.







                                        share|cite|improve this answer












                                        share|cite|improve this answer



                                        share|cite|improve this answer










                                        answered Mar 19 '14 at 4:16









                                        MCTMCT

                                        14.4k42667




                                        14.4k42667























                                            0












                                            $begingroup$

                                            Trivially $(a,b)mid ax+by$ (since $(a,b)mid a$ and $(a,b)mid b$).



                                            This shows ${ax+bymid x,yinmathbb Z}subseteq {n(a,b)mid ninmathbb Z}$.





                                            Now prove $exists x,yinmathbb Z$ such that $n(a,b)=ax+by$.$ (2)$



                                            Euclid's algorithm shows that $exists x_0,y_0inmathbb Z ((a,b)=ax_0+by_0)$. Use this to show $(2)$.



                                            This concludes that ${n(a,b)mid ninmathbb Z}subseteq{ax+bymid x,yinmathbb Z}$.






                                            share|cite|improve this answer









                                            $endgroup$


















                                              0












                                              $begingroup$

                                              Trivially $(a,b)mid ax+by$ (since $(a,b)mid a$ and $(a,b)mid b$).



                                              This shows ${ax+bymid x,yinmathbb Z}subseteq {n(a,b)mid ninmathbb Z}$.





                                              Now prove $exists x,yinmathbb Z$ such that $n(a,b)=ax+by$.$ (2)$



                                              Euclid's algorithm shows that $exists x_0,y_0inmathbb Z ((a,b)=ax_0+by_0)$. Use this to show $(2)$.



                                              This concludes that ${n(a,b)mid ninmathbb Z}subseteq{ax+bymid x,yinmathbb Z}$.






                                              share|cite|improve this answer









                                              $endgroup$
















                                                0












                                                0








                                                0





                                                $begingroup$

                                                Trivially $(a,b)mid ax+by$ (since $(a,b)mid a$ and $(a,b)mid b$).



                                                This shows ${ax+bymid x,yinmathbb Z}subseteq {n(a,b)mid ninmathbb Z}$.





                                                Now prove $exists x,yinmathbb Z$ such that $n(a,b)=ax+by$.$ (2)$



                                                Euclid's algorithm shows that $exists x_0,y_0inmathbb Z ((a,b)=ax_0+by_0)$. Use this to show $(2)$.



                                                This concludes that ${n(a,b)mid ninmathbb Z}subseteq{ax+bymid x,yinmathbb Z}$.






                                                share|cite|improve this answer









                                                $endgroup$



                                                Trivially $(a,b)mid ax+by$ (since $(a,b)mid a$ and $(a,b)mid b$).



                                                This shows ${ax+bymid x,yinmathbb Z}subseteq {n(a,b)mid ninmathbb Z}$.





                                                Now prove $exists x,yinmathbb Z$ such that $n(a,b)=ax+by$.$ (2)$



                                                Euclid's algorithm shows that $exists x_0,y_0inmathbb Z ((a,b)=ax_0+by_0)$. Use this to show $(2)$.



                                                This concludes that ${n(a,b)mid ninmathbb Z}subseteq{ax+bymid x,yinmathbb Z}$.







                                                share|cite|improve this answer












                                                share|cite|improve this answer



                                                share|cite|improve this answer










                                                answered Apr 4 '15 at 14:12









                                                user26486user26486

                                                9,29021948




                                                9,29021948






























                                                    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%2f717771%2fshow-a-bbb-zb-bbb-z-gcda-b-bbb-z%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

                                                    android studio warns about leanback feature tag usage required on manifest while using Unity exported app?

                                                    SQL update select statement

                                                    'app-layout' is not a known element: how to share Component with different Modules