If any LC is divisible by the GCD then it has a certain form.
$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.
elementary-number-theory greatest-common-divisor
$endgroup$
add a comment |
$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.
elementary-number-theory greatest-common-divisor
$endgroup$
$begingroup$
Did you find the solution useful?
$endgroup$
– OmG
May 31 '17 at 4:57
add a comment |
$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.
elementary-number-theory greatest-common-divisor
$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
elementary-number-theory greatest-common-divisor
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
add a comment |
$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
add a comment |
3 Answers
3
active
oldest
votes
$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.
$endgroup$
add a comment |
$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)$$
$endgroup$
add a comment |
$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.
$endgroup$
add a comment |
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
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
$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.
$endgroup$
add a comment |
$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.
$endgroup$
add a comment |
$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.
$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.
edited May 31 '17 at 4:49
answered May 31 '17 at 4:44


OmGOmG
2,537824
2,537824
add a comment |
add a comment |
$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)$$
$endgroup$
add a comment |
$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)$$
$endgroup$
add a comment |
$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)$$
$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)$$
edited Jan 29 at 20:51
answered May 31 '17 at 15:31
Bill DubuqueBill Dubuque
213k29196654
213k29196654
add a comment |
add a comment |
$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.
$endgroup$
add a comment |
$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.
$endgroup$
add a comment |
$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.
$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.
answered Jan 29 at 21:06
steven gregorysteven gregory
18.3k32358
18.3k32358
add a comment |
add a comment |
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.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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
$begingroup$
Did you find the solution useful?
$endgroup$
– OmG
May 31 '17 at 4:57