Prove that $gcd(a, b) = gcd(b, a-b)$












2












$begingroup$


I can understand the concept that $gcd(a, b) = gcd(b, r)$, where $a = bq + r$, which is grounded from the fact that $gcd(a, b) = gcd(b, a-b)$, but I have no intuition for the latter.






elementary-number-theory divisibility greatest-common-divisor







share|cite|improve this question











$endgroup$

















    2












    $begingroup$


    I can understand the concept that $gcd(a, b) = gcd(b, r)$, where $a = bq + r$, which is grounded from the fact that $gcd(a, b) = gcd(b, a-b)$, but I have no intuition for the latter.






    elementary-number-theory divisibility greatest-common-divisor







    share|cite|improve this question











    $endgroup$















      2












      2








      2


      1



      $begingroup$


      I can understand the concept that $gcd(a, b) = gcd(b, r)$, where $a = bq + r$, which is grounded from the fact that $gcd(a, b) = gcd(b, a-b)$, but I have no intuition for the latter.






      elementary-number-theory divisibility greatest-common-divisor







      share|cite|improve this question











      $endgroup$




      I can understand the concept that $gcd(a, b) = gcd(b, r)$, where $a = bq + r$, which is grounded from the fact that $gcd(a, b) = gcd(b, a-b)$, but I have no intuition for the latter.






      elementary-number-theory divisibility greatest-common-divisor




      elementary-number-theory divisibility greatest-common-divisor






      share|cite|improve this question















      share|cite|improve this question













      share|cite|improve this question




      share|cite|improve this question








      edited Oct 18 '17 at 12:02









      Martin Sleziak

      44.8k10119272




      44.8k10119272










      asked Oct 24 '14 at 5:58









      Joel ChristophelJoel Christophel

      324519




      324519






















          7 Answers
          7






          active

          oldest

          votes


















          2












          $begingroup$

          Lemma: $gcd(x,y)=d$ iff $d$ is the smallest natural number that can be expressed as a linear combination of $x$ and $y$ (in $mathbb{Z}$)



          We have $gcd(a,b)=d$



          $d=ap+bq$ for some $p,qin mathbb{Z}$



          $d=ap-bp+bp+bq=(a-b)p+b(p+q)=(a-b)p+bq'$



          where $q'=p+qin mathbb{Z}$



          Thus,



          $gcd(a-b,b)=d$






          share|cite|improve this answer











          $endgroup$













          • $begingroup$
            That lemma is only true in the forward direction. For example, $1cdot5+1cdot4=9$ but $gcd(5,4)=1neq9$.
            $endgroup$
            – Harry
            Oct 18 '17 at 12:14












          • $begingroup$
            Ah, I see. Would the converse be true if the condition of d being the smallest such positive natural number is added?
            $endgroup$
            – Swapnil Tripathi
            Oct 21 '17 at 1:17










          • $begingroup$
            yes, it would. The $gcd$ of $x,y$ is the smallest positive natural number that can be expressed as an integral linear combination of $x,y$.
            $endgroup$
            – Harry
            Oct 21 '17 at 2:02










          • $begingroup$
            Edited, thank you! @Harry
            $endgroup$
            – Swapnil Tripathi
            Oct 22 '17 at 18:32



















          2












          $begingroup$

          Let $d = text{gcd}(a,b)$, then $d|a$, and $d|b$, so $d|(a-b)$, and $d|mbox {gcd}(b,a-b)= d'$. Also $d'|b$, and $d'|(a-b)$, so $d'|(b+(a-b)) = a$, and $d'|mbox {gcd}(a,b) = d$. So $d = d'$.






          share|cite|improve this answer











          $endgroup$













          • $begingroup$
            How do you prove that $$d mid gcd(b, a-b)=d'$$
            $endgroup$
            – Dr. Mathva
            Jan 1 at 14:23



















          1












          $begingroup$

          Suppose $gcd(a, b) = q$ it means at least that $q | a, q|b$ then $q|(a - b)$. This is true for every divisor so that for $gcd$ also.



          One user asked converse but it is also obvious. Denote $s = a - b$, then $gcd(b, s) = gcd(b, s + b) = gcd(b, a)$.






          share|cite|improve this answer











          $endgroup$













          • $begingroup$
            You need to prove also the converse, if $q'|b$ and $q'|a-b$ then $q'|a$, but +1 anyway.
            $endgroup$
            – Jean-Claude Arbaut
            Oct 24 '14 at 6:02








          • 1




            $begingroup$
            It's just that your first statement only proved that $gcd(a,b)|gcd(b,a-b)$, not equality. ;-)
            $endgroup$
            – Jean-Claude Arbaut
            Oct 24 '14 at 6:15



















          0












          $begingroup$

          By definition
          $$gcd(a,b)=giff g|a,bland (forall h:h|a,bimplies hle g).$$



          Then



          $$begin{align}gcd(a,b)=g&implies g|a,bland (forall h:h|a,bimplies hle g)\&implies g|b,(a-b)land (forall h:h|b,(a-b)implies h|a,bimplies hle g)\&implies gcd(b,a-b)=g.end{align}$$






          share|cite|improve this answer









          $endgroup$





















            0












            $begingroup$

            Every common divisor of $a$ and $b$ is also a common divisor of $b$ and $a-b$.



            Every common divisor of $b$ and $a-b$ is also a common divisor of $a$ and $b$, as $a=(a-b)+b$.






            share|cite|improve this answer









            $endgroup$













            • $begingroup$
              This answer moves the problem from $gcd$ to divisors. $d$ divides $a$ and $b$ implies $d$ divides $apm b$ is a rather trivial property. ($a=md,b=ndimplies apm b=(mpm n)d$.)
              $endgroup$
              – Yves Daoust
              Oct 26 '14 at 21:00





















            0












            $begingroup$

            $dmid a-b$ means $dfrac{a-b}d=dfrac ad-dfrac bd$ is an integer. It's clear that if one of these fractions is an integer, then so is the other, i.e., $dmid aiff dmid b$.



            $dmidgcd(b,a-b)implies dmid b$, thus $dmid a$.



            Therefore a divisor of both $a-b$ and $b$ is also a divisor of $a$.



            Conversely, $kmid a$ means $dfrac ak=dfrac{a-b}k+dfrac bk$ is an integer, so $kmid a-biff kmid b$.



            $kmidgcd(a,b)implies kmid b$, thus $kmid a-b$.



            Therefore a divisor of both $a$ and $b$ is also a divisor of $a-b$. QED






            share|cite|improve this answer











            $endgroup$





















              0












              $begingroup$

              Write $u=b$ and $v=a-b$. Then $a=u+v$ and $b=u$.



              These two sets of equations imply that $d$ divides $u,v$ iff $d$ divides $a,b$. Therefore, $gcd(u,v)=gcd(a,b)$.



              In algebra terms, the equations imply that ${a,b}$ and ${u,v}$ generate the same subgroup of $mathbb Z$. It's well known that $langle x,y rangle = gcd(x,y)mathbb Z$, hence the result.






              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%2f988690%2fprove-that-gcda-b-gcdb-a-b%23new-answer', 'question_page');
                }
                );

                Post as a guest















                Required, but never shown

























                7 Answers
                7






                active

                oldest

                votes








                7 Answers
                7






                active

                oldest

                votes









                active

                oldest

                votes






                active

                oldest

                votes









                2












                $begingroup$

                Lemma: $gcd(x,y)=d$ iff $d$ is the smallest natural number that can be expressed as a linear combination of $x$ and $y$ (in $mathbb{Z}$)



                We have $gcd(a,b)=d$



                $d=ap+bq$ for some $p,qin mathbb{Z}$



                $d=ap-bp+bp+bq=(a-b)p+b(p+q)=(a-b)p+bq'$



                where $q'=p+qin mathbb{Z}$



                Thus,



                $gcd(a-b,b)=d$






                share|cite|improve this answer











                $endgroup$













                • $begingroup$
                  That lemma is only true in the forward direction. For example, $1cdot5+1cdot4=9$ but $gcd(5,4)=1neq9$.
                  $endgroup$
                  – Harry
                  Oct 18 '17 at 12:14












                • $begingroup$
                  Ah, I see. Would the converse be true if the condition of d being the smallest such positive natural number is added?
                  $endgroup$
                  – Swapnil Tripathi
                  Oct 21 '17 at 1:17










                • $begingroup$
                  yes, it would. The $gcd$ of $x,y$ is the smallest positive natural number that can be expressed as an integral linear combination of $x,y$.
                  $endgroup$
                  – Harry
                  Oct 21 '17 at 2:02










                • $begingroup$
                  Edited, thank you! @Harry
                  $endgroup$
                  – Swapnil Tripathi
                  Oct 22 '17 at 18:32
















                2












                $begingroup$

                Lemma: $gcd(x,y)=d$ iff $d$ is the smallest natural number that can be expressed as a linear combination of $x$ and $y$ (in $mathbb{Z}$)



                We have $gcd(a,b)=d$



                $d=ap+bq$ for some $p,qin mathbb{Z}$



                $d=ap-bp+bp+bq=(a-b)p+b(p+q)=(a-b)p+bq'$



                where $q'=p+qin mathbb{Z}$



                Thus,



                $gcd(a-b,b)=d$






                share|cite|improve this answer











                $endgroup$













                • $begingroup$
                  That lemma is only true in the forward direction. For example, $1cdot5+1cdot4=9$ but $gcd(5,4)=1neq9$.
                  $endgroup$
                  – Harry
                  Oct 18 '17 at 12:14












                • $begingroup$
                  Ah, I see. Would the converse be true if the condition of d being the smallest such positive natural number is added?
                  $endgroup$
                  – Swapnil Tripathi
                  Oct 21 '17 at 1:17










                • $begingroup$
                  yes, it would. The $gcd$ of $x,y$ is the smallest positive natural number that can be expressed as an integral linear combination of $x,y$.
                  $endgroup$
                  – Harry
                  Oct 21 '17 at 2:02










                • $begingroup$
                  Edited, thank you! @Harry
                  $endgroup$
                  – Swapnil Tripathi
                  Oct 22 '17 at 18:32














                2












                2








                2





                $begingroup$

                Lemma: $gcd(x,y)=d$ iff $d$ is the smallest natural number that can be expressed as a linear combination of $x$ and $y$ (in $mathbb{Z}$)



                We have $gcd(a,b)=d$



                $d=ap+bq$ for some $p,qin mathbb{Z}$



                $d=ap-bp+bp+bq=(a-b)p+b(p+q)=(a-b)p+bq'$



                where $q'=p+qin mathbb{Z}$



                Thus,



                $gcd(a-b,b)=d$






                share|cite|improve this answer











                $endgroup$



                Lemma: $gcd(x,y)=d$ iff $d$ is the smallest natural number that can be expressed as a linear combination of $x$ and $y$ (in $mathbb{Z}$)



                We have $gcd(a,b)=d$



                $d=ap+bq$ for some $p,qin mathbb{Z}$



                $d=ap-bp+bp+bq=(a-b)p+b(p+q)=(a-b)p+bq'$



                where $q'=p+qin mathbb{Z}$



                Thus,



                $gcd(a-b,b)=d$







                share|cite|improve this answer














                share|cite|improve this answer



                share|cite|improve this answer








                edited Oct 22 '17 at 18:31

























                answered Oct 24 '14 at 6:12









                Swapnil TripathiSwapnil Tripathi

                3,08621936




                3,08621936












                • $begingroup$
                  That lemma is only true in the forward direction. For example, $1cdot5+1cdot4=9$ but $gcd(5,4)=1neq9$.
                  $endgroup$
                  – Harry
                  Oct 18 '17 at 12:14












                • $begingroup$
                  Ah, I see. Would the converse be true if the condition of d being the smallest such positive natural number is added?
                  $endgroup$
                  – Swapnil Tripathi
                  Oct 21 '17 at 1:17










                • $begingroup$
                  yes, it would. The $gcd$ of $x,y$ is the smallest positive natural number that can be expressed as an integral linear combination of $x,y$.
                  $endgroup$
                  – Harry
                  Oct 21 '17 at 2:02










                • $begingroup$
                  Edited, thank you! @Harry
                  $endgroup$
                  – Swapnil Tripathi
                  Oct 22 '17 at 18:32


















                • $begingroup$
                  That lemma is only true in the forward direction. For example, $1cdot5+1cdot4=9$ but $gcd(5,4)=1neq9$.
                  $endgroup$
                  – Harry
                  Oct 18 '17 at 12:14












                • $begingroup$
                  Ah, I see. Would the converse be true if the condition of d being the smallest such positive natural number is added?
                  $endgroup$
                  – Swapnil Tripathi
                  Oct 21 '17 at 1:17










                • $begingroup$
                  yes, it would. The $gcd$ of $x,y$ is the smallest positive natural number that can be expressed as an integral linear combination of $x,y$.
                  $endgroup$
                  – Harry
                  Oct 21 '17 at 2:02










                • $begingroup$
                  Edited, thank you! @Harry
                  $endgroup$
                  – Swapnil Tripathi
                  Oct 22 '17 at 18:32
















                $begingroup$
                That lemma is only true in the forward direction. For example, $1cdot5+1cdot4=9$ but $gcd(5,4)=1neq9$.
                $endgroup$
                – Harry
                Oct 18 '17 at 12:14






                $begingroup$
                That lemma is only true in the forward direction. For example, $1cdot5+1cdot4=9$ but $gcd(5,4)=1neq9$.
                $endgroup$
                – Harry
                Oct 18 '17 at 12:14














                $begingroup$
                Ah, I see. Would the converse be true if the condition of d being the smallest such positive natural number is added?
                $endgroup$
                – Swapnil Tripathi
                Oct 21 '17 at 1:17




                $begingroup$
                Ah, I see. Would the converse be true if the condition of d being the smallest such positive natural number is added?
                $endgroup$
                – Swapnil Tripathi
                Oct 21 '17 at 1:17












                $begingroup$
                yes, it would. The $gcd$ of $x,y$ is the smallest positive natural number that can be expressed as an integral linear combination of $x,y$.
                $endgroup$
                – Harry
                Oct 21 '17 at 2:02




                $begingroup$
                yes, it would. The $gcd$ of $x,y$ is the smallest positive natural number that can be expressed as an integral linear combination of $x,y$.
                $endgroup$
                – Harry
                Oct 21 '17 at 2:02












                $begingroup$
                Edited, thank you! @Harry
                $endgroup$
                – Swapnil Tripathi
                Oct 22 '17 at 18:32




                $begingroup$
                Edited, thank you! @Harry
                $endgroup$
                – Swapnil Tripathi
                Oct 22 '17 at 18:32











                2












                $begingroup$

                Let $d = text{gcd}(a,b)$, then $d|a$, and $d|b$, so $d|(a-b)$, and $d|mbox {gcd}(b,a-b)= d'$. Also $d'|b$, and $d'|(a-b)$, so $d'|(b+(a-b)) = a$, and $d'|mbox {gcd}(a,b) = d$. So $d = d'$.






                share|cite|improve this answer











                $endgroup$













                • $begingroup$
                  How do you prove that $$d mid gcd(b, a-b)=d'$$
                  $endgroup$
                  – Dr. Mathva
                  Jan 1 at 14:23
















                2












                $begingroup$

                Let $d = text{gcd}(a,b)$, then $d|a$, and $d|b$, so $d|(a-b)$, and $d|mbox {gcd}(b,a-b)= d'$. Also $d'|b$, and $d'|(a-b)$, so $d'|(b+(a-b)) = a$, and $d'|mbox {gcd}(a,b) = d$. So $d = d'$.






                share|cite|improve this answer











                $endgroup$













                • $begingroup$
                  How do you prove that $$d mid gcd(b, a-b)=d'$$
                  $endgroup$
                  – Dr. Mathva
                  Jan 1 at 14:23














                2












                2








                2





                $begingroup$

                Let $d = text{gcd}(a,b)$, then $d|a$, and $d|b$, so $d|(a-b)$, and $d|mbox {gcd}(b,a-b)= d'$. Also $d'|b$, and $d'|(a-b)$, so $d'|(b+(a-b)) = a$, and $d'|mbox {gcd}(a,b) = d$. So $d = d'$.






                share|cite|improve this answer











                $endgroup$



                Let $d = text{gcd}(a,b)$, then $d|a$, and $d|b$, so $d|(a-b)$, and $d|mbox {gcd}(b,a-b)= d'$. Also $d'|b$, and $d'|(a-b)$, so $d'|(b+(a-b)) = a$, and $d'|mbox {gcd}(a,b) = d$. So $d = d'$.







                share|cite|improve this answer














                share|cite|improve this answer



                share|cite|improve this answer








                edited Jan 1 at 14:46









                user376343

                3,9234829




                3,9234829










                answered Oct 24 '14 at 6:07









                DeepSeaDeepSea

                71.3k54488




                71.3k54488












                • $begingroup$
                  How do you prove that $$d mid gcd(b, a-b)=d'$$
                  $endgroup$
                  – Dr. Mathva
                  Jan 1 at 14:23


















                • $begingroup$
                  How do you prove that $$d mid gcd(b, a-b)=d'$$
                  $endgroup$
                  – Dr. Mathva
                  Jan 1 at 14:23
















                $begingroup$
                How do you prove that $$d mid gcd(b, a-b)=d'$$
                $endgroup$
                – Dr. Mathva
                Jan 1 at 14:23




                $begingroup$
                How do you prove that $$d mid gcd(b, a-b)=d'$$
                $endgroup$
                – Dr. Mathva
                Jan 1 at 14:23











                1












                $begingroup$

                Suppose $gcd(a, b) = q$ it means at least that $q | a, q|b$ then $q|(a - b)$. This is true for every divisor so that for $gcd$ also.



                One user asked converse but it is also obvious. Denote $s = a - b$, then $gcd(b, s) = gcd(b, s + b) = gcd(b, a)$.






                share|cite|improve this answer











                $endgroup$













                • $begingroup$
                  You need to prove also the converse, if $q'|b$ and $q'|a-b$ then $q'|a$, but +1 anyway.
                  $endgroup$
                  – Jean-Claude Arbaut
                  Oct 24 '14 at 6:02








                • 1




                  $begingroup$
                  It's just that your first statement only proved that $gcd(a,b)|gcd(b,a-b)$, not equality. ;-)
                  $endgroup$
                  – Jean-Claude Arbaut
                  Oct 24 '14 at 6:15
















                1












                $begingroup$

                Suppose $gcd(a, b) = q$ it means at least that $q | a, q|b$ then $q|(a - b)$. This is true for every divisor so that for $gcd$ also.



                One user asked converse but it is also obvious. Denote $s = a - b$, then $gcd(b, s) = gcd(b, s + b) = gcd(b, a)$.






                share|cite|improve this answer











                $endgroup$













                • $begingroup$
                  You need to prove also the converse, if $q'|b$ and $q'|a-b$ then $q'|a$, but +1 anyway.
                  $endgroup$
                  – Jean-Claude Arbaut
                  Oct 24 '14 at 6:02








                • 1




                  $begingroup$
                  It's just that your first statement only proved that $gcd(a,b)|gcd(b,a-b)$, not equality. ;-)
                  $endgroup$
                  – Jean-Claude Arbaut
                  Oct 24 '14 at 6:15














                1












                1








                1





                $begingroup$

                Suppose $gcd(a, b) = q$ it means at least that $q | a, q|b$ then $q|(a - b)$. This is true for every divisor so that for $gcd$ also.



                One user asked converse but it is also obvious. Denote $s = a - b$, then $gcd(b, s) = gcd(b, s + b) = gcd(b, a)$.






                share|cite|improve this answer











                $endgroup$



                Suppose $gcd(a, b) = q$ it means at least that $q | a, q|b$ then $q|(a - b)$. This is true for every divisor so that for $gcd$ also.



                One user asked converse but it is also obvious. Denote $s = a - b$, then $gcd(b, s) = gcd(b, s + b) = gcd(b, a)$.







                share|cite|improve this answer














                share|cite|improve this answer



                share|cite|improve this answer








                edited Oct 24 '14 at 6:08

























                answered Oct 24 '14 at 6:01









                JihadJihad

                38417




                38417












                • $begingroup$
                  You need to prove also the converse, if $q'|b$ and $q'|a-b$ then $q'|a$, but +1 anyway.
                  $endgroup$
                  – Jean-Claude Arbaut
                  Oct 24 '14 at 6:02








                • 1




                  $begingroup$
                  It's just that your first statement only proved that $gcd(a,b)|gcd(b,a-b)$, not equality. ;-)
                  $endgroup$
                  – Jean-Claude Arbaut
                  Oct 24 '14 at 6:15


















                • $begingroup$
                  You need to prove also the converse, if $q'|b$ and $q'|a-b$ then $q'|a$, but +1 anyway.
                  $endgroup$
                  – Jean-Claude Arbaut
                  Oct 24 '14 at 6:02








                • 1




                  $begingroup$
                  It's just that your first statement only proved that $gcd(a,b)|gcd(b,a-b)$, not equality. ;-)
                  $endgroup$
                  – Jean-Claude Arbaut
                  Oct 24 '14 at 6:15
















                $begingroup$
                You need to prove also the converse, if $q'|b$ and $q'|a-b$ then $q'|a$, but +1 anyway.
                $endgroup$
                – Jean-Claude Arbaut
                Oct 24 '14 at 6:02






                $begingroup$
                You need to prove also the converse, if $q'|b$ and $q'|a-b$ then $q'|a$, but +1 anyway.
                $endgroup$
                – Jean-Claude Arbaut
                Oct 24 '14 at 6:02






                1




                1




                $begingroup$
                It's just that your first statement only proved that $gcd(a,b)|gcd(b,a-b)$, not equality. ;-)
                $endgroup$
                – Jean-Claude Arbaut
                Oct 24 '14 at 6:15




                $begingroup$
                It's just that your first statement only proved that $gcd(a,b)|gcd(b,a-b)$, not equality. ;-)
                $endgroup$
                – Jean-Claude Arbaut
                Oct 24 '14 at 6:15











                0












                $begingroup$

                By definition
                $$gcd(a,b)=giff g|a,bland (forall h:h|a,bimplies hle g).$$



                Then



                $$begin{align}gcd(a,b)=g&implies g|a,bland (forall h:h|a,bimplies hle g)\&implies g|b,(a-b)land (forall h:h|b,(a-b)implies h|a,bimplies hle g)\&implies gcd(b,a-b)=g.end{align}$$






                share|cite|improve this answer









                $endgroup$


















                  0












                  $begingroup$

                  By definition
                  $$gcd(a,b)=giff g|a,bland (forall h:h|a,bimplies hle g).$$



                  Then



                  $$begin{align}gcd(a,b)=g&implies g|a,bland (forall h:h|a,bimplies hle g)\&implies g|b,(a-b)land (forall h:h|b,(a-b)implies h|a,bimplies hle g)\&implies gcd(b,a-b)=g.end{align}$$






                  share|cite|improve this answer









                  $endgroup$
















                    0












                    0








                    0





                    $begingroup$

                    By definition
                    $$gcd(a,b)=giff g|a,bland (forall h:h|a,bimplies hle g).$$



                    Then



                    $$begin{align}gcd(a,b)=g&implies g|a,bland (forall h:h|a,bimplies hle g)\&implies g|b,(a-b)land (forall h:h|b,(a-b)implies h|a,bimplies hle g)\&implies gcd(b,a-b)=g.end{align}$$






                    share|cite|improve this answer









                    $endgroup$



                    By definition
                    $$gcd(a,b)=giff g|a,bland (forall h:h|a,bimplies hle g).$$



                    Then



                    $$begin{align}gcd(a,b)=g&implies g|a,bland (forall h:h|a,bimplies hle g)\&implies g|b,(a-b)land (forall h:h|b,(a-b)implies h|a,bimplies hle g)\&implies gcd(b,a-b)=g.end{align}$$







                    share|cite|improve this answer












                    share|cite|improve this answer



                    share|cite|improve this answer










                    answered Oct 24 '14 at 7:35









                    Yves DaoustYves Daoust

                    129k675227




                    129k675227























                        0












                        $begingroup$

                        Every common divisor of $a$ and $b$ is also a common divisor of $b$ and $a-b$.



                        Every common divisor of $b$ and $a-b$ is also a common divisor of $a$ and $b$, as $a=(a-b)+b$.






                        share|cite|improve this answer









                        $endgroup$













                        • $begingroup$
                          This answer moves the problem from $gcd$ to divisors. $d$ divides $a$ and $b$ implies $d$ divides $apm b$ is a rather trivial property. ($a=md,b=ndimplies apm b=(mpm n)d$.)
                          $endgroup$
                          – Yves Daoust
                          Oct 26 '14 at 21:00


















                        0












                        $begingroup$

                        Every common divisor of $a$ and $b$ is also a common divisor of $b$ and $a-b$.



                        Every common divisor of $b$ and $a-b$ is also a common divisor of $a$ and $b$, as $a=(a-b)+b$.






                        share|cite|improve this answer









                        $endgroup$













                        • $begingroup$
                          This answer moves the problem from $gcd$ to divisors. $d$ divides $a$ and $b$ implies $d$ divides $apm b$ is a rather trivial property. ($a=md,b=ndimplies apm b=(mpm n)d$.)
                          $endgroup$
                          – Yves Daoust
                          Oct 26 '14 at 21:00
















                        0












                        0








                        0





                        $begingroup$

                        Every common divisor of $a$ and $b$ is also a common divisor of $b$ and $a-b$.



                        Every common divisor of $b$ and $a-b$ is also a common divisor of $a$ and $b$, as $a=(a-b)+b$.






                        share|cite|improve this answer









                        $endgroup$



                        Every common divisor of $a$ and $b$ is also a common divisor of $b$ and $a-b$.



                        Every common divisor of $b$ and $a-b$ is also a common divisor of $a$ and $b$, as $a=(a-b)+b$.







                        share|cite|improve this answer












                        share|cite|improve this answer



                        share|cite|improve this answer










                        answered Oct 24 '14 at 7:48









                        Yves DaoustYves Daoust

                        129k675227




                        129k675227












                        • $begingroup$
                          This answer moves the problem from $gcd$ to divisors. $d$ divides $a$ and $b$ implies $d$ divides $apm b$ is a rather trivial property. ($a=md,b=ndimplies apm b=(mpm n)d$.)
                          $endgroup$
                          – Yves Daoust
                          Oct 26 '14 at 21:00




















                        • $begingroup$
                          This answer moves the problem from $gcd$ to divisors. $d$ divides $a$ and $b$ implies $d$ divides $apm b$ is a rather trivial property. ($a=md,b=ndimplies apm b=(mpm n)d$.)
                          $endgroup$
                          – Yves Daoust
                          Oct 26 '14 at 21:00


















                        $begingroup$
                        This answer moves the problem from $gcd$ to divisors. $d$ divides $a$ and $b$ implies $d$ divides $apm b$ is a rather trivial property. ($a=md,b=ndimplies apm b=(mpm n)d$.)
                        $endgroup$
                        – Yves Daoust
                        Oct 26 '14 at 21:00






                        $begingroup$
                        This answer moves the problem from $gcd$ to divisors. $d$ divides $a$ and $b$ implies $d$ divides $apm b$ is a rather trivial property. ($a=md,b=ndimplies apm b=(mpm n)d$.)
                        $endgroup$
                        – Yves Daoust
                        Oct 26 '14 at 21:00













                        0












                        $begingroup$

                        $dmid a-b$ means $dfrac{a-b}d=dfrac ad-dfrac bd$ is an integer. It's clear that if one of these fractions is an integer, then so is the other, i.e., $dmid aiff dmid b$.



                        $dmidgcd(b,a-b)implies dmid b$, thus $dmid a$.



                        Therefore a divisor of both $a-b$ and $b$ is also a divisor of $a$.



                        Conversely, $kmid a$ means $dfrac ak=dfrac{a-b}k+dfrac bk$ is an integer, so $kmid a-biff kmid b$.



                        $kmidgcd(a,b)implies kmid b$, thus $kmid a-b$.



                        Therefore a divisor of both $a$ and $b$ is also a divisor of $a-b$. QED






                        share|cite|improve this answer











                        $endgroup$


















                          0












                          $begingroup$

                          $dmid a-b$ means $dfrac{a-b}d=dfrac ad-dfrac bd$ is an integer. It's clear that if one of these fractions is an integer, then so is the other, i.e., $dmid aiff dmid b$.



                          $dmidgcd(b,a-b)implies dmid b$, thus $dmid a$.



                          Therefore a divisor of both $a-b$ and $b$ is also a divisor of $a$.



                          Conversely, $kmid a$ means $dfrac ak=dfrac{a-b}k+dfrac bk$ is an integer, so $kmid a-biff kmid b$.



                          $kmidgcd(a,b)implies kmid b$, thus $kmid a-b$.



                          Therefore a divisor of both $a$ and $b$ is also a divisor of $a-b$. QED






                          share|cite|improve this answer











                          $endgroup$
















                            0












                            0








                            0





                            $begingroup$

                            $dmid a-b$ means $dfrac{a-b}d=dfrac ad-dfrac bd$ is an integer. It's clear that if one of these fractions is an integer, then so is the other, i.e., $dmid aiff dmid b$.



                            $dmidgcd(b,a-b)implies dmid b$, thus $dmid a$.



                            Therefore a divisor of both $a-b$ and $b$ is also a divisor of $a$.



                            Conversely, $kmid a$ means $dfrac ak=dfrac{a-b}k+dfrac bk$ is an integer, so $kmid a-biff kmid b$.



                            $kmidgcd(a,b)implies kmid b$, thus $kmid a-b$.



                            Therefore a divisor of both $a$ and $b$ is also a divisor of $a-b$. QED






                            share|cite|improve this answer











                            $endgroup$



                            $dmid a-b$ means $dfrac{a-b}d=dfrac ad-dfrac bd$ is an integer. It's clear that if one of these fractions is an integer, then so is the other, i.e., $dmid aiff dmid b$.



                            $dmidgcd(b,a-b)implies dmid b$, thus $dmid a$.



                            Therefore a divisor of both $a-b$ and $b$ is also a divisor of $a$.



                            Conversely, $kmid a$ means $dfrac ak=dfrac{a-b}k+dfrac bk$ is an integer, so $kmid a-biff kmid b$.



                            $kmidgcd(a,b)implies kmid b$, thus $kmid a-b$.



                            Therefore a divisor of both $a$ and $b$ is also a divisor of $a-b$. QED







                            share|cite|improve this answer














                            share|cite|improve this answer



                            share|cite|improve this answer








                            edited Jan 29 '15 at 9:58

























                            answered Oct 25 '14 at 22:32









                            Jaycob ColemanJaycob Coleman

                            413524




                            413524























                                0












                                $begingroup$

                                Write $u=b$ and $v=a-b$. Then $a=u+v$ and $b=u$.



                                These two sets of equations imply that $d$ divides $u,v$ iff $d$ divides $a,b$. Therefore, $gcd(u,v)=gcd(a,b)$.



                                In algebra terms, the equations imply that ${a,b}$ and ${u,v}$ generate the same subgroup of $mathbb Z$. It's well known that $langle x,y rangle = gcd(x,y)mathbb Z$, hence the result.






                                share|cite|improve this answer









                                $endgroup$


















                                  0












                                  $begingroup$

                                  Write $u=b$ and $v=a-b$. Then $a=u+v$ and $b=u$.



                                  These two sets of equations imply that $d$ divides $u,v$ iff $d$ divides $a,b$. Therefore, $gcd(u,v)=gcd(a,b)$.



                                  In algebra terms, the equations imply that ${a,b}$ and ${u,v}$ generate the same subgroup of $mathbb Z$. It's well known that $langle x,y rangle = gcd(x,y)mathbb Z$, hence the result.






                                  share|cite|improve this answer









                                  $endgroup$
















                                    0












                                    0








                                    0





                                    $begingroup$

                                    Write $u=b$ and $v=a-b$. Then $a=u+v$ and $b=u$.



                                    These two sets of equations imply that $d$ divides $u,v$ iff $d$ divides $a,b$. Therefore, $gcd(u,v)=gcd(a,b)$.



                                    In algebra terms, the equations imply that ${a,b}$ and ${u,v}$ generate the same subgroup of $mathbb Z$. It's well known that $langle x,y rangle = gcd(x,y)mathbb Z$, hence the result.






                                    share|cite|improve this answer









                                    $endgroup$



                                    Write $u=b$ and $v=a-b$. Then $a=u+v$ and $b=u$.



                                    These two sets of equations imply that $d$ divides $u,v$ iff $d$ divides $a,b$. Therefore, $gcd(u,v)=gcd(a,b)$.



                                    In algebra terms, the equations imply that ${a,b}$ and ${u,v}$ generate the same subgroup of $mathbb Z$. It's well known that $langle x,y rangle = gcd(x,y)mathbb Z$, hence the result.







                                    share|cite|improve this answer












                                    share|cite|improve this answer



                                    share|cite|improve this answer










                                    answered Jan 29 '15 at 10:38









                                    lhflhf

                                    166k10171396




                                    166k10171396






























                                        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%2f988690%2fprove-that-gcda-b-gcdb-a-b%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

                                        Bressuire

                                        Image
                                        .mw-parser-output .infobox{border:1px solid #aaa;background-color:#f9f9f9;color:black;margin:.5em 0 .5em 1em;padding:.2em;float:right;clear:right;width:22em;text-align:left;font-size:88%;line-height:1.6em}.mw-parser-output .infobox td,.mw-parser-output .infobox th{vertical-align:top;padding:0 .2em}.mw-parser-output .infobox caption{font-size:larger}.mw-parser-output .infobox.bordered{border-collapse:collapse}.mw-parser-output .infobox.bordered td,.mw-parser-output .infobox.bordered th{border:1px solid #aaa}.mw-parser-output .infobox.bordered .borderless td,.mw-parser-output .infobox.bordered .borderless th{border:0}.mw-parser-output .infobox-showbutton .mw-collapsible-text{color:inherit}.mw-parser-output .infobox.bordered .mergedtoprow td,.mw-parser-output .infobox.bordered .mergedtoprow th{border:0;border-top:1px solid #aaa;border-right:1px solid #aaa}.mw-parser-output .infobox.bordered .mergedrow td,.mw-parser-output .infobox.bordered .mergedrow th{border:0;border-right:1px solid
                                        Read more

                                        Cabo Verde

                                        Image
                                          Nota: Cabo-verdiano redireciona para este artigo. Para a língua falada em Cabo Verde, veja crioulo cabo-verdiano. Para outros significados, veja Cabo Verde (desambiguação). Coordenadas: 14° 55' N 23° 31' O Cabo Verde República de Cabo Verde Bandeira Brasão de Armas Lema: Unidade, Trabalho, Progresso Hino nacional: Cântico da Liberdade Gentílico: cabo-verdiano [ 1 ] Capital Praia 14° 55' N 23° 31' O Cidade mais populosa Praia Língua oficial Português Governo República unitária semipresidencialista [ 2 ]  - Presidente Jorge Carlos Fonseca  - Primeiro-ministro Ulisses Correia e Silva História    - Descoberta 1460   - Independência 00 • de Portugal 5 de Julho de 1975   - Multipartidarismo 13 de Janeiro de 1990  Área    - Total 4 033 km² (146.º)  - Água (%) 0,08 População    - Estimativa para 2017 560 899 [ 3 ] hab. (173.º)
                                        Read more

                                        Gyllenstierna

                                        Image
                                        .mw-parser-output .infobox{border:1px solid #aaa;background-color:#f9f9f9;color:black;margin:.5em 0 .5em 1em;padding:.2em;float:right;clear:right;width:22em;text-align:left;font-size:88%;line-height:1.6em}.mw-parser-output .infobox td,.mw-parser-output .infobox th{vertical-align:top;padding:0 .2em}.mw-parser-output .infobox caption{font-size:larger}.mw-parser-output .infobox.bordered{border-collapse:collapse}.mw-parser-output .infobox.bordered td,.mw-parser-output .infobox.bordered th{border:1px solid #aaa}.mw-parser-output .infobox.bordered .borderless td,.mw-parser-output .infobox.bordered .borderless th{border:0}.mw-parser-output .infobox-showbutton .mw-collapsible-text{color:inherit}.mw-parser-output .infobox.bordered .mergedtoprow td,.mw-parser-output .infobox.bordered .mergedtoprow th{border:0;border-top:1px solid #aaa;border-right:1px solid #aaa}.mw-parser-output .infobox.bordered .mergedrow td,.mw-parser-output .infobox.bordered .mergedrow th{border:0;border-right:1px solid
                                        Read more