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,8733829




                3,8733829










                answered Oct 24 '14 at 6:07









                DeepSeaDeepSea

                71.3k54487




                71.3k54487












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

                                        Quarter-circle Tiles

                                        Image
                                        up vote 0 down vote favorite I have $99$ identical square tiles, each with a quarter-circle drawn on it like this: [asy] size(1.5cm); draw(Arc((2,0),1,90,180),red+1); draw((0,0)--(2,0)--(2,2)--(0,2)--(0,0)); [/asy] When I arrange the tiles in a $9times 11$ rectangular grid, each with a random orientation, what is the expected value of the number of full circles I form? I think this problem has to do with finding the chance any given 2x2 square has a circle, but I can't find it. expected-value share | cite | improve this question asked Nov 20 at 15:03 6minecraftninja 1 2
                                        Read more

                                        build a pushdown automaton that recognizes the reverse language of a given pushdown automaton?

                                        Image
                                        0 I think it's similiar to NFAs. I replace the finite states of the given automaton for start-states for my new automaton. I do it with $epsilon$ -transition from the start state to the actual finite states of the given automaton. The start state of the given automaton will be my accepting(finite) state of my new one. All transitions will be reversed of course to recognize the reversed word. But how do I have to change the stack of the pushdown automaton? That's tricky. formal-languages automata context-free-grammar share | cite | improve this question edited Nov 29 '18 at 14:20 joee
                                        Read more

                                        Mont Emei

                                        Image
                                        Mont Emei.mw-parser-output .entete.map{background-image:url("//upload.wikimedia.org/wikipedia/commons/7/7a/Picto_infobox_map.png")} Vue du sommet Wanfo du mont Emei Géographie Altitude 3 099  m , Wanfo Coordonnées 29° 31′ 11″ nord, 103° 19′ 57″ est Administration Pays   Chine Province Sichuan Ville-préfecture Leshan Géolocalisation sur la carte : Sichuan Mont Emei Géolocalisation sur la carte : Chine Mont Emei modifier   Paysage panoramique du mont Emei, incluant le paysage panoramique du grand Bouddha de Leshan *   Patrimoine mondial de l'UNESCO Passerelle en bois sur le versant ouest Pays   Chine Subdivision Sichuan Type Mixte Critères (iv) (vi) (x) Superficie 15 400 ha Numéro d’identification 779 Zone géographique Asie et Pacifique  ** Année d’inscription 1996 (20 e session) * Descriptif officiel UNESCO ** Classification géog
                                        Read more