If any LC is divisible by the GCD then it has a certain form.












0












$begingroup$


Let $a,b$ be given integers and $gcd(a,b)|n$, which implies by a theorem that I have that there are some integers $x_0,y_0$ such that $n=ax_0+by_0$. Moreover, suppose that $x,y$ are two other integers such that $n=ax+by$.



I need to show that $x$ has the form $x_0+frac{tb}{gcd(a,b)}$ and $y$ has the form $y_0-frac{ta}{gcd(a,b)}$ for some appropriate choice of integer $t$. I was given the hint to prove this by contradiction but I saw absolutely no path forward using that.



Since $n=ax_0+by_0=ax+by$ I can infer $a(x-x_0)=-b(y-y_0)$. I can also see that my goal amounts to proving the existence of an integer $t$ such that



$$(x-x_0)cdot gcd(a,b) = tb\ (y-y_0)cdot gcd(a,b)=-ta$$



This vaguely resembles the statement that $b$ divides the left-hand side of the first equation, and likewise for $a$, although it's a little more than that. One thing that comes to mind is that $|ab| = gcd(a,b)lcm(a,b)$ but I'm not seeing how I could use that. Thought about maybe arguing that since $a(x-x_0)=-b(y-y_0)$ then either $b|a$ or $b|x-x_0$ but that only holds for prime $b$.



Any help would be appreciated.










share|cite|improve this question











$endgroup$












  • $begingroup$
    Did you find the solution useful?
    $endgroup$
    – OmG
    May 31 '17 at 4:57
















0












$begingroup$


Let $a,b$ be given integers and $gcd(a,b)|n$, which implies by a theorem that I have that there are some integers $x_0,y_0$ such that $n=ax_0+by_0$. Moreover, suppose that $x,y$ are two other integers such that $n=ax+by$.



I need to show that $x$ has the form $x_0+frac{tb}{gcd(a,b)}$ and $y$ has the form $y_0-frac{ta}{gcd(a,b)}$ for some appropriate choice of integer $t$. I was given the hint to prove this by contradiction but I saw absolutely no path forward using that.



Since $n=ax_0+by_0=ax+by$ I can infer $a(x-x_0)=-b(y-y_0)$. I can also see that my goal amounts to proving the existence of an integer $t$ such that



$$(x-x_0)cdot gcd(a,b) = tb\ (y-y_0)cdot gcd(a,b)=-ta$$



This vaguely resembles the statement that $b$ divides the left-hand side of the first equation, and likewise for $a$, although it's a little more than that. One thing that comes to mind is that $|ab| = gcd(a,b)lcm(a,b)$ but I'm not seeing how I could use that. Thought about maybe arguing that since $a(x-x_0)=-b(y-y_0)$ then either $b|a$ or $b|x-x_0$ but that only holds for prime $b$.



Any help would be appreciated.










share|cite|improve this question











$endgroup$












  • $begingroup$
    Did you find the solution useful?
    $endgroup$
    – OmG
    May 31 '17 at 4:57














0












0








0


1



$begingroup$


Let $a,b$ be given integers and $gcd(a,b)|n$, which implies by a theorem that I have that there are some integers $x_0,y_0$ such that $n=ax_0+by_0$. Moreover, suppose that $x,y$ are two other integers such that $n=ax+by$.



I need to show that $x$ has the form $x_0+frac{tb}{gcd(a,b)}$ and $y$ has the form $y_0-frac{ta}{gcd(a,b)}$ for some appropriate choice of integer $t$. I was given the hint to prove this by contradiction but I saw absolutely no path forward using that.



Since $n=ax_0+by_0=ax+by$ I can infer $a(x-x_0)=-b(y-y_0)$. I can also see that my goal amounts to proving the existence of an integer $t$ such that



$$(x-x_0)cdot gcd(a,b) = tb\ (y-y_0)cdot gcd(a,b)=-ta$$



This vaguely resembles the statement that $b$ divides the left-hand side of the first equation, and likewise for $a$, although it's a little more than that. One thing that comes to mind is that $|ab| = gcd(a,b)lcm(a,b)$ but I'm not seeing how I could use that. Thought about maybe arguing that since $a(x-x_0)=-b(y-y_0)$ then either $b|a$ or $b|x-x_0$ but that only holds for prime $b$.



Any help would be appreciated.










share|cite|improve this question











$endgroup$




Let $a,b$ be given integers and $gcd(a,b)|n$, which implies by a theorem that I have that there are some integers $x_0,y_0$ such that $n=ax_0+by_0$. Moreover, suppose that $x,y$ are two other integers such that $n=ax+by$.



I need to show that $x$ has the form $x_0+frac{tb}{gcd(a,b)}$ and $y$ has the form $y_0-frac{ta}{gcd(a,b)}$ for some appropriate choice of integer $t$. I was given the hint to prove this by contradiction but I saw absolutely no path forward using that.



Since $n=ax_0+by_0=ax+by$ I can infer $a(x-x_0)=-b(y-y_0)$. I can also see that my goal amounts to proving the existence of an integer $t$ such that



$$(x-x_0)cdot gcd(a,b) = tb\ (y-y_0)cdot gcd(a,b)=-ta$$



This vaguely resembles the statement that $b$ divides the left-hand side of the first equation, and likewise for $a$, although it's a little more than that. One thing that comes to mind is that $|ab| = gcd(a,b)lcm(a,b)$ but I'm not seeing how I could use that. Thought about maybe arguing that since $a(x-x_0)=-b(y-y_0)$ then either $b|a$ or $b|x-x_0$ but that only holds for prime $b$.



Any help would be appreciated.







elementary-number-theory greatest-common-divisor






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited May 31 '17 at 15:37









Bill Dubuque

213k29196654




213k29196654










asked May 31 '17 at 4:26









AddemAddem

1,7561429




1,7561429












  • $begingroup$
    Did you find the solution useful?
    $endgroup$
    – OmG
    May 31 '17 at 4:57


















  • $begingroup$
    Did you find the solution useful?
    $endgroup$
    – OmG
    May 31 '17 at 4:57
















$begingroup$
Did you find the solution useful?
$endgroup$
– OmG
May 31 '17 at 4:57




$begingroup$
Did you find the solution useful?
$endgroup$
– OmG
May 31 '17 at 4:57










3 Answers
3






active

oldest

votes


















1












$begingroup$

We know $a(x-x_0) = -b(y-y_0), a = gcd(a,b)times c, b = gcd(a,b)times d$, and $gcd(c,d) = 1$, so
$$gcd(a,b)times c (x-x_0)= -b(y-y_0) Rightarrow x -x_0 = frac{-(y-y_0)}{c}b times frac{1}{gcd(a,b)}$$



Therefore:
$$x = x_0 + frac{tb}{gcd(a,b)}$$
Which is $t = frac{y_0 - y}{c}$.
So we should show $frac{y-y_0}{c}$ is an integer number. To show this:



$a(x-x_0) = -b(y-y_0) Rightarrow gcd(a,b) times c (x-x_0) = -gcd(a,b) times d (y-y_0)Rightarrow x-x_0 = d(y-y_0)/c$



as we know $x-x_0$ is integer, and $gcd(c,d) = 1$, so $frac{y-y_0}{c}$ is an integer.






share|cite|improve this answer











$endgroup$





















    1












    $begingroup$

    It's clearer if we bring to the fore the innate linear structure. Since $,ax+by,$ is linear in $,x,y,,$ the general solution of $ ax+by=n $ is the sum of any particular solution $,(x_0,y_0),$ plus the general solution solution of the associated homogeneous equation $,ax+by = 0iff x/y = -b/a,,$ which is $,(x,y)= n(-bar b,bar a),,$ where $,bar a/bar b,$ is the lowest terms rep of $,a/b,,$ i.e. where $,bar a,bar b,$ are coprime. Summing these two components gives the general solution



    $$,(x,y), =, (x_0,y_0)+n(-bar b,bar a), =, (x_0-nbar b,,y_0 + nbar a)$$






    share|cite|improve this answer











    $endgroup$





















      0












      $begingroup$

      This is a different way of doing what @OMG did.



      $a(x-x_0) = -b(y-y_0) implies dfrac{a}{gcd(a,b)}(x-x_0) = -dfrac{b}{gcd(a,b)}(y-y_0)$



      Hence $dfrac{a}{gcd(a,b)} bigg | dfrac{b}{gcd(a,b)}(y-y_0)$.



      But $gcdleft( dfrac{a}{gcd(a,b)}, dfrac{b}{gcd(a,b)} right) = 1$.



      Thus we must have
      $dfrac{a}{gcd(a,b)} bigg | (y-y_0)$.



      So, for some integer $t$, we must have $y-y_0 = tdfrac{a}{gcd(a,b)}$. The rest follows.






      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%2f2303701%2fif-any-lc-is-divisible-by-the-gcd-then-it-has-a-certain-form%23new-answer', 'question_page');
        }
        );

        Post as a guest















        Required, but never shown

























        3 Answers
        3






        active

        oldest

        votes








        3 Answers
        3






        active

        oldest

        votes









        active

        oldest

        votes






        active

        oldest

        votes









        1












        $begingroup$

        We know $a(x-x_0) = -b(y-y_0), a = gcd(a,b)times c, b = gcd(a,b)times d$, and $gcd(c,d) = 1$, so
        $$gcd(a,b)times c (x-x_0)= -b(y-y_0) Rightarrow x -x_0 = frac{-(y-y_0)}{c}b times frac{1}{gcd(a,b)}$$



        Therefore:
        $$x = x_0 + frac{tb}{gcd(a,b)}$$
        Which is $t = frac{y_0 - y}{c}$.
        So we should show $frac{y-y_0}{c}$ is an integer number. To show this:



        $a(x-x_0) = -b(y-y_0) Rightarrow gcd(a,b) times c (x-x_0) = -gcd(a,b) times d (y-y_0)Rightarrow x-x_0 = d(y-y_0)/c$



        as we know $x-x_0$ is integer, and $gcd(c,d) = 1$, so $frac{y-y_0}{c}$ is an integer.






        share|cite|improve this answer











        $endgroup$


















          1












          $begingroup$

          We know $a(x-x_0) = -b(y-y_0), a = gcd(a,b)times c, b = gcd(a,b)times d$, and $gcd(c,d) = 1$, so
          $$gcd(a,b)times c (x-x_0)= -b(y-y_0) Rightarrow x -x_0 = frac{-(y-y_0)}{c}b times frac{1}{gcd(a,b)}$$



          Therefore:
          $$x = x_0 + frac{tb}{gcd(a,b)}$$
          Which is $t = frac{y_0 - y}{c}$.
          So we should show $frac{y-y_0}{c}$ is an integer number. To show this:



          $a(x-x_0) = -b(y-y_0) Rightarrow gcd(a,b) times c (x-x_0) = -gcd(a,b) times d (y-y_0)Rightarrow x-x_0 = d(y-y_0)/c$



          as we know $x-x_0$ is integer, and $gcd(c,d) = 1$, so $frac{y-y_0}{c}$ is an integer.






          share|cite|improve this answer











          $endgroup$
















            1












            1








            1





            $begingroup$

            We know $a(x-x_0) = -b(y-y_0), a = gcd(a,b)times c, b = gcd(a,b)times d$, and $gcd(c,d) = 1$, so
            $$gcd(a,b)times c (x-x_0)= -b(y-y_0) Rightarrow x -x_0 = frac{-(y-y_0)}{c}b times frac{1}{gcd(a,b)}$$



            Therefore:
            $$x = x_0 + frac{tb}{gcd(a,b)}$$
            Which is $t = frac{y_0 - y}{c}$.
            So we should show $frac{y-y_0}{c}$ is an integer number. To show this:



            $a(x-x_0) = -b(y-y_0) Rightarrow gcd(a,b) times c (x-x_0) = -gcd(a,b) times d (y-y_0)Rightarrow x-x_0 = d(y-y_0)/c$



            as we know $x-x_0$ is integer, and $gcd(c,d) = 1$, so $frac{y-y_0}{c}$ is an integer.






            share|cite|improve this answer











            $endgroup$



            We know $a(x-x_0) = -b(y-y_0), a = gcd(a,b)times c, b = gcd(a,b)times d$, and $gcd(c,d) = 1$, so
            $$gcd(a,b)times c (x-x_0)= -b(y-y_0) Rightarrow x -x_0 = frac{-(y-y_0)}{c}b times frac{1}{gcd(a,b)}$$



            Therefore:
            $$x = x_0 + frac{tb}{gcd(a,b)}$$
            Which is $t = frac{y_0 - y}{c}$.
            So we should show $frac{y-y_0}{c}$ is an integer number. To show this:



            $a(x-x_0) = -b(y-y_0) Rightarrow gcd(a,b) times c (x-x_0) = -gcd(a,b) times d (y-y_0)Rightarrow x-x_0 = d(y-y_0)/c$



            as we know $x-x_0$ is integer, and $gcd(c,d) = 1$, so $frac{y-y_0}{c}$ is an integer.







            share|cite|improve this answer














            share|cite|improve this answer



            share|cite|improve this answer








            edited May 31 '17 at 4:49

























            answered May 31 '17 at 4:44









            OmGOmG

            2,537824




            2,537824























                1












                $begingroup$

                It's clearer if we bring to the fore the innate linear structure. Since $,ax+by,$ is linear in $,x,y,,$ the general solution of $ ax+by=n $ is the sum of any particular solution $,(x_0,y_0),$ plus the general solution solution of the associated homogeneous equation $,ax+by = 0iff x/y = -b/a,,$ which is $,(x,y)= n(-bar b,bar a),,$ where $,bar a/bar b,$ is the lowest terms rep of $,a/b,,$ i.e. where $,bar a,bar b,$ are coprime. Summing these two components gives the general solution



                $$,(x,y), =, (x_0,y_0)+n(-bar b,bar a), =, (x_0-nbar b,,y_0 + nbar a)$$






                share|cite|improve this answer











                $endgroup$


















                  1












                  $begingroup$

                  It's clearer if we bring to the fore the innate linear structure. Since $,ax+by,$ is linear in $,x,y,,$ the general solution of $ ax+by=n $ is the sum of any particular solution $,(x_0,y_0),$ plus the general solution solution of the associated homogeneous equation $,ax+by = 0iff x/y = -b/a,,$ which is $,(x,y)= n(-bar b,bar a),,$ where $,bar a/bar b,$ is the lowest terms rep of $,a/b,,$ i.e. where $,bar a,bar b,$ are coprime. Summing these two components gives the general solution



                  $$,(x,y), =, (x_0,y_0)+n(-bar b,bar a), =, (x_0-nbar b,,y_0 + nbar a)$$






                  share|cite|improve this answer











                  $endgroup$
















                    1












                    1








                    1





                    $begingroup$

                    It's clearer if we bring to the fore the innate linear structure. Since $,ax+by,$ is linear in $,x,y,,$ the general solution of $ ax+by=n $ is the sum of any particular solution $,(x_0,y_0),$ plus the general solution solution of the associated homogeneous equation $,ax+by = 0iff x/y = -b/a,,$ which is $,(x,y)= n(-bar b,bar a),,$ where $,bar a/bar b,$ is the lowest terms rep of $,a/b,,$ i.e. where $,bar a,bar b,$ are coprime. Summing these two components gives the general solution



                    $$,(x,y), =, (x_0,y_0)+n(-bar b,bar a), =, (x_0-nbar b,,y_0 + nbar a)$$






                    share|cite|improve this answer











                    $endgroup$



                    It's clearer if we bring to the fore the innate linear structure. Since $,ax+by,$ is linear in $,x,y,,$ the general solution of $ ax+by=n $ is the sum of any particular solution $,(x_0,y_0),$ plus the general solution solution of the associated homogeneous equation $,ax+by = 0iff x/y = -b/a,,$ which is $,(x,y)= n(-bar b,bar a),,$ where $,bar a/bar b,$ is the lowest terms rep of $,a/b,,$ i.e. where $,bar a,bar b,$ are coprime. Summing these two components gives the general solution



                    $$,(x,y), =, (x_0,y_0)+n(-bar b,bar a), =, (x_0-nbar b,,y_0 + nbar a)$$







                    share|cite|improve this answer














                    share|cite|improve this answer



                    share|cite|improve this answer








                    edited Jan 29 at 20:51

























                    answered May 31 '17 at 15:31









                    Bill DubuqueBill Dubuque

                    213k29196654




                    213k29196654























                        0












                        $begingroup$

                        This is a different way of doing what @OMG did.



                        $a(x-x_0) = -b(y-y_0) implies dfrac{a}{gcd(a,b)}(x-x_0) = -dfrac{b}{gcd(a,b)}(y-y_0)$



                        Hence $dfrac{a}{gcd(a,b)} bigg | dfrac{b}{gcd(a,b)}(y-y_0)$.



                        But $gcdleft( dfrac{a}{gcd(a,b)}, dfrac{b}{gcd(a,b)} right) = 1$.



                        Thus we must have
                        $dfrac{a}{gcd(a,b)} bigg | (y-y_0)$.



                        So, for some integer $t$, we must have $y-y_0 = tdfrac{a}{gcd(a,b)}$. The rest follows.






                        share|cite|improve this answer









                        $endgroup$


















                          0












                          $begingroup$

                          This is a different way of doing what @OMG did.



                          $a(x-x_0) = -b(y-y_0) implies dfrac{a}{gcd(a,b)}(x-x_0) = -dfrac{b}{gcd(a,b)}(y-y_0)$



                          Hence $dfrac{a}{gcd(a,b)} bigg | dfrac{b}{gcd(a,b)}(y-y_0)$.



                          But $gcdleft( dfrac{a}{gcd(a,b)}, dfrac{b}{gcd(a,b)} right) = 1$.



                          Thus we must have
                          $dfrac{a}{gcd(a,b)} bigg | (y-y_0)$.



                          So, for some integer $t$, we must have $y-y_0 = tdfrac{a}{gcd(a,b)}$. The rest follows.






                          share|cite|improve this answer









                          $endgroup$
















                            0












                            0








                            0





                            $begingroup$

                            This is a different way of doing what @OMG did.



                            $a(x-x_0) = -b(y-y_0) implies dfrac{a}{gcd(a,b)}(x-x_0) = -dfrac{b}{gcd(a,b)}(y-y_0)$



                            Hence $dfrac{a}{gcd(a,b)} bigg | dfrac{b}{gcd(a,b)}(y-y_0)$.



                            But $gcdleft( dfrac{a}{gcd(a,b)}, dfrac{b}{gcd(a,b)} right) = 1$.



                            Thus we must have
                            $dfrac{a}{gcd(a,b)} bigg | (y-y_0)$.



                            So, for some integer $t$, we must have $y-y_0 = tdfrac{a}{gcd(a,b)}$. The rest follows.






                            share|cite|improve this answer









                            $endgroup$



                            This is a different way of doing what @OMG did.



                            $a(x-x_0) = -b(y-y_0) implies dfrac{a}{gcd(a,b)}(x-x_0) = -dfrac{b}{gcd(a,b)}(y-y_0)$



                            Hence $dfrac{a}{gcd(a,b)} bigg | dfrac{b}{gcd(a,b)}(y-y_0)$.



                            But $gcdleft( dfrac{a}{gcd(a,b)}, dfrac{b}{gcd(a,b)} right) = 1$.



                            Thus we must have
                            $dfrac{a}{gcd(a,b)} bigg | (y-y_0)$.



                            So, for some integer $t$, we must have $y-y_0 = tdfrac{a}{gcd(a,b)}$. The rest follows.







                            share|cite|improve this answer












                            share|cite|improve this answer



                            share|cite|improve this answer










                            answered Jan 29 at 21:06









                            steven gregorysteven gregory

                            18.3k32358




                            18.3k32358






























                                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%2f2303701%2fif-any-lc-is-divisible-by-the-gcd-then-it-has-a-certain-form%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

                                MongoDB - Not Authorized To Execute Command

                                How to fix TextFormField cause rebuild widget in Flutter

                                in spring boot 2.1 many test slices are not allowed anymore due to multiple @BootstrapWith