Smallest positive integer that can be expressed as a linear combination of two integers
$begingroup$
I've recently gotten in number theory, using Theory of Numbers by Andrew Adler as a starting point and came across a theorem that states,
Suppose a and b are not 0, let d = (a, b). Then d is the smallest positive integer that can be expressed as a linear combination of a and b.
Is the converse true, i.e. if I find an integer that is the smallest positive integer which is a linear combination of two integers a and b, then it must be the greatest common divisor of a and b? For example, if I found out 1 = xa + yb for some integer x and b, must 1 be the greatest common divisor, since it is the smallest positive integer possible?
number-theory
asked Dec 21 '18 at 2:32
aeseaaesea
82
$endgroup$
|
show 1 more comment
$begingroup$
I've recently gotten in number theory, using Theory of Numbers by Andrew Adler as a starting point and came across a theorem that states,
Suppose a and b are not 0, let d = (a, b). Then d is the smallest positive integer that can be expressed as a linear combination of a and b.
Is the converse true, i.e. if I find an integer that is the smallest positive integer which is a linear combination of two integers a and b, then it must be the greatest common divisor of a and b? For example, if I found out 1 = xa + yb for some integer x and b, must 1 be the greatest common divisor, since it is the smallest positive integer possible?
number-theory
asked Dec 21 '18 at 2:32
aeseaaesea
82
$endgroup$
$begingroup$
Consider the case where $gcd(a,b) neq 1$ and what that would say about what would need to be factors of $xa + yb$ for any integers $x$ and $b$.
$endgroup$
– John Omielan
Dec 21 '18 at 3:20
$begingroup$
@JohnOmielan gcd(a, b) itself would divide all the linear combinations of xa + yb, meaning it would also divide the smallest one, where gcd(a, b) is less than or equal to it right? How would I go around proving that gcd(a, b) is equal to the linear combination?
$endgroup$
– aesea
Dec 21 '18 at 3:40
$begingroup$
A small correction to my comment is that the end should say "$x$ and $y$".
$endgroup$
– John Omielan
Dec 21 '18 at 3:40
$begingroup$
As $gcd(a,b)$ is a positive integer and it must divide all linear combinations of $xa + yb$, then how can any positive value be smaller, as it would mean that any such smaller value divided by $gcd(a,b)$ would be a non-integral fraction, which contradicts what it means for $gcd(a,b)$ to divide the value. I hope this is fairly clear.
$endgroup$
– John Omielan
Dec 21 '18 at 3:47
$begingroup$
I understand that there are no positive values that are less than the gcd(a, b) itself, but I can't seem to wrap my head around the fact that the smallest linear combination of a and b must be the greatest common divisor of both.
$endgroup$
– aesea
Dec 21 '18 at 3:57
|
show 1 more comment
$begingroup$
I've recently gotten in number theory, using Theory of Numbers by Andrew Adler as a starting point and came across a theorem that states,
Suppose a and b are not 0, let d = (a, b). Then d is the smallest positive integer that can be expressed as a linear combination of a and b.
Is the converse true, i.e. if I find an integer that is the smallest positive integer which is a linear combination of two integers a and b, then it must be the greatest common divisor of a and b? For example, if I found out 1 = xa + yb for some integer x and b, must 1 be the greatest common divisor, since it is the smallest positive integer possible?
number-theory
asked Dec 21 '18 at 2:32
aeseaaesea
82
$endgroup$
I've recently gotten in number theory, using Theory of Numbers by Andrew Adler as a starting point and came across a theorem that states,
Suppose a and b are not 0, let d = (a, b). Then d is the smallest positive integer that can be expressed as a linear combination of a and b.
Is the converse true, i.e. if I find an integer that is the smallest positive integer which is a linear combination of two integers a and b, then it must be the greatest common divisor of a and b? For example, if I found out 1 = xa + yb for some integer x and b, must 1 be the greatest common divisor, since it is the smallest positive integer possible?
number-theory
number-theory
asked Dec 21 '18 at 2:32
aeseaaesea
82
asked Dec 21 '18 at 2:32
aeseaaesea
82
asked Dec 21 '18 at 2:32
aeseaaesea
82
asked Dec 21 '18 at 2:32
aeseaaesea
82
asked Dec 21 '18 at 2:32
aeseaaesea
82
82
$begingroup$
Consider the case where $gcd(a,b) neq 1$ and what that would say about what would need to be factors of $xa + yb$ for any integers $x$ and $b$.
$endgroup$
– John Omielan
Dec 21 '18 at 3:20
$begingroup$
@JohnOmielan gcd(a, b) itself would divide all the linear combinations of xa + yb, meaning it would also divide the smallest one, where gcd(a, b) is less than or equal to it right? How would I go around proving that gcd(a, b) is equal to the linear combination?
$endgroup$
– aesea
Dec 21 '18 at 3:40
$begingroup$
A small correction to my comment is that the end should say "$x$ and $y$".
$endgroup$
– John Omielan
Dec 21 '18 at 3:40
$begingroup$
As $gcd(a,b)$ is a positive integer and it must divide all linear combinations of $xa + yb$, then how can any positive value be smaller, as it would mean that any such smaller value divided by $gcd(a,b)$ would be a non-integral fraction, which contradicts what it means for $gcd(a,b)$ to divide the value. I hope this is fairly clear.
$endgroup$
– John Omielan
Dec 21 '18 at 3:47
$begingroup$
I understand that there are no positive values that are less than the gcd(a, b) itself, but I can't seem to wrap my head around the fact that the smallest linear combination of a and b must be the greatest common divisor of both.
$endgroup$
– aesea
Dec 21 '18 at 3:57
|
show 1 more comment
$begingroup$
Consider the case where $gcd(a,b) neq 1$ and what that would say about what would need to be factors of $xa + yb$ for any integers $x$ and $b$.
$endgroup$
– John Omielan
Dec 21 '18 at 3:20
$begingroup$
@JohnOmielan gcd(a, b) itself would divide all the linear combinations of xa + yb, meaning it would also divide the smallest one, where gcd(a, b) is less than or equal to it right? How would I go around proving that gcd(a, b) is equal to the linear combination?
$endgroup$
– aesea
Dec 21 '18 at 3:40
$begingroup$
A small correction to my comment is that the end should say "$x$ and $y$".
$endgroup$
– John Omielan
Dec 21 '18 at 3:40
$begingroup$
As $gcd(a,b)$ is a positive integer and it must divide all linear combinations of $xa + yb$, then how can any positive value be smaller, as it would mean that any such smaller value divided by $gcd(a,b)$ would be a non-integral fraction, which contradicts what it means for $gcd(a,b)$ to divide the value. I hope this is fairly clear.
$endgroup$
– John Omielan
Dec 21 '18 at 3:47
$begingroup$
I understand that there are no positive values that are less than the gcd(a, b) itself, but I can't seem to wrap my head around the fact that the smallest linear combination of a and b must be the greatest common divisor of both.
$endgroup$
– aesea
Dec 21 '18 at 3:57
$begingroup$
Consider the case where $gcd(a,b) neq 1$ and what that would say about what would need to be factors of $xa + yb$ for any integers $x$ and $b$.
$endgroup$
– John Omielan
Dec 21 '18 at 3:20
$begingroup$
Consider the case where $gcd(a,b) neq 1$ and what that would say about what would need to be factors of $xa + yb$ for any integers $x$ and $b$.
$endgroup$
– John Omielan
Dec 21 '18 at 3:20
$begingroup$
@JohnOmielan gcd(a, b) itself would divide all the linear combinations of xa + yb, meaning it would also divide the smallest one, where gcd(a, b) is less than or equal to it right? How would I go around proving that gcd(a, b) is equal to the linear combination?
$endgroup$
– aesea
Dec 21 '18 at 3:40
$begingroup$
@JohnOmielan gcd(a, b) itself would divide all the linear combinations of xa + yb, meaning it would also divide the smallest one, where gcd(a, b) is less than or equal to it right? How would I go around proving that gcd(a, b) is equal to the linear combination?
$endgroup$
– aesea
Dec 21 '18 at 3:40
$begingroup$
A small correction to my comment is that the end should say "$x$ and $y$".
$endgroup$
– John Omielan
Dec 21 '18 at 3:40
$begingroup$
A small correction to my comment is that the end should say "$x$ and $y$".
$endgroup$
– John Omielan
Dec 21 '18 at 3:40
$begingroup$
As $gcd(a,b)$ is a positive integer and it must divide all linear combinations of $xa + yb$, then how can any positive value be smaller, as it would mean that any such smaller value divided by $gcd(a,b)$ would be a non-integral fraction, which contradicts what it means for $gcd(a,b)$ to divide the value. I hope this is fairly clear.
$endgroup$
– John Omielan
Dec 21 '18 at 3:47
$begingroup$
As $gcd(a,b)$ is a positive integer and it must divide all linear combinations of $xa + yb$, then how can any positive value be smaller, as it would mean that any such smaller value divided by $gcd(a,b)$ would be a non-integral fraction, which contradicts what it means for $gcd(a,b)$ to divide the value. I hope this is fairly clear.
$endgroup$
– John Omielan
Dec 21 '18 at 3:47
$begingroup$
I understand that there are no positive values that are less than the gcd(a, b) itself, but I can't seem to wrap my head around the fact that the smallest linear combination of a and b must be the greatest common divisor of both.
$endgroup$
– aesea
Dec 21 '18 at 3:57
$begingroup$
I understand that there are no positive values that are less than the gcd(a, b) itself, but I can't seem to wrap my head around the fact that the smallest linear combination of a and b must be the greatest common divisor of both.
$endgroup$
– aesea
Dec 21 '18 at 3:57
|
show 1 more comment
1 Answer
1
active
oldest
votes
$begingroup$
It's an equivalence. That is, we have an if and only if.
For the "converse", recall that we have that by Bezout's identity, $(a,b)$ can be written as a linear combination of $a$ and $b$ (this involves the Euclidean algorithm). So if $d$ is the smallest number that has this property, we have $dle (a,b)$. But of course $dge (a,b)$, since any number dividing $a$ and $b$ divides $d$ (by the fact that $d$ is a linear combination of $a$ and $b$). So $d=(a,b)$.
answered Dec 21 '18 at 4:47
Chris CusterChris Custer
14k3827
$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%2f3048124%2fsmallest-positive-integer-that-can-be-expressed-as-a-linear-combination-of-two-i%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
It's an equivalence. That is, we have an if and only if.
For the "converse", recall that we have that by Bezout's identity, $(a,b)$ can be written as a linear combination of $a$ and $b$ (this involves the Euclidean algorithm). So if $d$ is the smallest number that has this property, we have $dle (a,b)$. But of course $dge (a,b)$, since any number dividing $a$ and $b$ divides $d$ (by the fact that $d$ is a linear combination of $a$ and $b$). So $d=(a,b)$.
answered Dec 21 '18 at 4:47
Chris CusterChris Custer
14k3827
$endgroup$
add a comment |
$begingroup$
It's an equivalence. That is, we have an if and only if.
For the "converse", recall that we have that by Bezout's identity, $(a,b)$ can be written as a linear combination of $a$ and $b$ (this involves the Euclidean algorithm). So if $d$ is the smallest number that has this property, we have $dle (a,b)$. But of course $dge (a,b)$, since any number dividing $a$ and $b$ divides $d$ (by the fact that $d$ is a linear combination of $a$ and $b$). So $d=(a,b)$.
answered Dec 21 '18 at 4:47
Chris CusterChris Custer
14k3827
$endgroup$
add a comment |
$begingroup$
It's an equivalence. That is, we have an if and only if.
For the "converse", recall that we have that by Bezout's identity, $(a,b)$ can be written as a linear combination of $a$ and $b$ (this involves the Euclidean algorithm). So if $d$ is the smallest number that has this property, we have $dle (a,b)$. But of course $dge (a,b)$, since any number dividing $a$ and $b$ divides $d$ (by the fact that $d$ is a linear combination of $a$ and $b$). So $d=(a,b)$.
answered Dec 21 '18 at 4:47
Chris CusterChris Custer
14k3827
$endgroup$
It's an equivalence. That is, we have an if and only if.
For the "converse", recall that we have that by Bezout's identity, $(a,b)$ can be written as a linear combination of $a$ and $b$ (this involves the Euclidean algorithm). So if $d$ is the smallest number that has this property, we have $dle (a,b)$. But of course $dge (a,b)$, since any number dividing $a$ and $b$ divides $d$ (by the fact that $d$ is a linear combination of $a$ and $b$). So $d=(a,b)$.
answered Dec 21 '18 at 4:47
Chris CusterChris Custer
14k3827
answered Dec 21 '18 at 4:47
Chris CusterChris Custer
14k3827
answered Dec 21 '18 at 4:47
Chris CusterChris Custer
14k3827
answered Dec 21 '18 at 4:47
Chris CusterChris Custer
14k3827
14k3827
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%2f3048124%2fsmallest-positive-integer-that-can-be-expressed-as-a-linear-combination-of-two-i%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$
Consider the case where $gcd(a,b) neq 1$ and what that would say about what would need to be factors of $xa + yb$ for any integers $x$ and $b$.
$endgroup$
– John Omielan
Dec 21 '18 at 3:20
$begingroup$
@JohnOmielan gcd(a, b) itself would divide all the linear combinations of xa + yb, meaning it would also divide the smallest one, where gcd(a, b) is less than or equal to it right? How would I go around proving that gcd(a, b) is equal to the linear combination?
$endgroup$
– aesea
Dec 21 '18 at 3:40
$begingroup$
A small correction to my comment is that the end should say "$x$ and $y$".
$endgroup$
– John Omielan
Dec 21 '18 at 3:40
$begingroup$
As $gcd(a,b)$ is a positive integer and it must divide all linear combinations of $xa + yb$, then how can any positive value be smaller, as it would mean that any such smaller value divided by $gcd(a,b)$ would be a non-integral fraction, which contradicts what it means for $gcd(a,b)$ to divide the value. I hope this is fairly clear.
$endgroup$
– John Omielan
Dec 21 '18 at 3:47
$begingroup$
I understand that there are no positive values that are less than the gcd(a, b) itself, but I can't seem to wrap my head around the fact that the smallest linear combination of a and b must be the greatest common divisor of both.
$endgroup$
– aesea
Dec 21 '18 at 3:57