Bezout's identity: which half is larger? [closed]
up vote
0
down vote
favorite
Bezout's identity: Let a and b be integers with greatest common divisor d. Then, there exist integers x and y such that ax + by = d.
Is it true that if a > b then ax < by? Is there a proof for this?
greatest-common-divisor
asked Nov 13 at 0:52
user5464854
1
closed as unclear what you're asking by Shailesh, Leucippus, Rushabh Mehta, Lord Shark the Unknown, ancientmathematician Nov 13 at 9:49
Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.
add a comment |
up vote
0
down vote
favorite
Bezout's identity: Let a and b be integers with greatest common divisor d. Then, there exist integers x and y such that ax + by = d.
Is it true that if a > b then ax < by? Is there a proof for this?
greatest-common-divisor
asked Nov 13 at 0:52
user5464854
1
closed as unclear what you're asking by Shailesh, Leucippus, Rushabh Mehta, Lord Shark the Unknown, ancientmathematician Nov 13 at 9:49
Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.
1
This is a little confusing, since one of $x$ and $y$ must be negative if $a$ and $b$ are both positive.
– Ethan Bolker
Nov 13 at 0:56
add a comment |
up vote
0
down vote
favorite
up vote
0
down vote
favorite
Bezout's identity: Let a and b be integers with greatest common divisor d. Then, there exist integers x and y such that ax + by = d.
Is it true that if a > b then ax < by? Is there a proof for this?
greatest-common-divisor
asked Nov 13 at 0:52
user5464854
1
Bezout's identity: Let a and b be integers with greatest common divisor d. Then, there exist integers x and y such that ax + by = d.
Is it true that if a > b then ax < by? Is there a proof for this?
greatest-common-divisor
greatest-common-divisor
asked Nov 13 at 0:52
user5464854
1
asked Nov 13 at 0:52
user5464854
1
asked Nov 13 at 0:52
user5464854
1
asked Nov 13 at 0:52
user5464854
1
asked Nov 13 at 0:52
user5464854
1
1
closed as unclear what you're asking by Shailesh, Leucippus, Rushabh Mehta, Lord Shark the Unknown, ancientmathematician Nov 13 at 9:49
Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.
closed as unclear what you're asking by Shailesh, Leucippus, Rushabh Mehta, Lord Shark the Unknown, ancientmathematician Nov 13 at 9:49
Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.
1
This is a little confusing, since one of $x$ and $y$ must be negative if $a$ and $b$ are both positive.
– Ethan Bolker
Nov 13 at 0:56
add a comment |
1
This is a little confusing, since one of $x$ and $y$ must be negative if $a$ and $b$ are both positive.
– Ethan Bolker
Nov 13 at 0:56
1
1
This is a little confusing, since one of $x$ and $y$ must be negative if $a$ and $b$ are both positive.
– Ethan Bolker
Nov 13 at 0:56
This is a little confusing, since one of $x$ and $y$ must be negative if $a$ and $b$ are both positive.
– Ethan Bolker
Nov 13 at 0:56
add a comment |
1 Answer
1
active
oldest
votes
up vote
2
down vote
$x,y$ are not uniquely defined. Let $a=2,b=1$. Then we could take $x=1, y=-1$, which makes your inequality false. Or we could take $x=-1.y=3$ which would make it true.
Note: In the comments, the OP has made clear that $x,y$ are intended to be the "minimal" solution, that is, the solution generated by the Euclidean Algorithm. In my example, the minimal solution is, of course, $x=0, y=1$ for which the claim holds. But even with this extra requirement, however, the general claim is false. For $a=3,b=2$, the minimal solution is $x=1,y=-1$, say.
answered Nov 13 at 0:55
lulu
37.8k24476
probably worth mentioning that, if $a,b$ are positive, unless $a|b$ or $b|a,$ then one of $x,y$ is positive and the other negative.
– Will Jagy
Nov 13 at 0:58
@WillJagy Sure, though a priori the OP might imagine that, in that situation, we always needed $x<0, y>0$ (which, to be sure, we don't).
– lulu
Nov 13 at 0:59
Sorry, I was thinking about the Extended Euclidean algorithm. Are x, y uniquely defined in that?
– user5464854
Nov 13 at 1:09
@user5464854 Ah. The coefficients generated by Euclid are indeed well defined, in fact they are the "smallest" solutions. You can read more about that here.
– lulu
Nov 13 at 10:43
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
$x,y$ are not uniquely defined. Let $a=2,b=1$. Then we could take $x=1, y=-1$, which makes your inequality false. Or we could take $x=-1.y=3$ which would make it true.
Note: In the comments, the OP has made clear that $x,y$ are intended to be the "minimal" solution, that is, the solution generated by the Euclidean Algorithm. In my example, the minimal solution is, of course, $x=0, y=1$ for which the claim holds. But even with this extra requirement, however, the general claim is false. For $a=3,b=2$, the minimal solution is $x=1,y=-1$, say.
answered Nov 13 at 0:55
lulu
37.8k24476
probably worth mentioning that, if $a,b$ are positive, unless $a|b$ or $b|a,$ then one of $x,y$ is positive and the other negative.
– Will Jagy
Nov 13 at 0:58
@WillJagy Sure, though a priori the OP might imagine that, in that situation, we always needed $x<0, y>0$ (which, to be sure, we don't).
– lulu
Nov 13 at 0:59
Sorry, I was thinking about the Extended Euclidean algorithm. Are x, y uniquely defined in that?
– user5464854
Nov 13 at 1:09
@user5464854 Ah. The coefficients generated by Euclid are indeed well defined, in fact they are the "smallest" solutions. You can read more about that here.
– lulu
Nov 13 at 10:43
add a comment |
up vote
2
down vote
$x,y$ are not uniquely defined. Let $a=2,b=1$. Then we could take $x=1, y=-1$, which makes your inequality false. Or we could take $x=-1.y=3$ which would make it true.
Note: In the comments, the OP has made clear that $x,y$ are intended to be the "minimal" solution, that is, the solution generated by the Euclidean Algorithm. In my example, the minimal solution is, of course, $x=0, y=1$ for which the claim holds. But even with this extra requirement, however, the general claim is false. For $a=3,b=2$, the minimal solution is $x=1,y=-1$, say.
answered Nov 13 at 0:55
lulu
37.8k24476
probably worth mentioning that, if $a,b$ are positive, unless $a|b$ or $b|a,$ then one of $x,y$ is positive and the other negative.
– Will Jagy
Nov 13 at 0:58
@WillJagy Sure, though a priori the OP might imagine that, in that situation, we always needed $x<0, y>0$ (which, to be sure, we don't).
– lulu
Nov 13 at 0:59
Sorry, I was thinking about the Extended Euclidean algorithm. Are x, y uniquely defined in that?
– user5464854
Nov 13 at 1:09
@user5464854 Ah. The coefficients generated by Euclid are indeed well defined, in fact they are the "smallest" solutions. You can read more about that here.
– lulu
Nov 13 at 10:43
add a comment |
up vote
2
down vote
up vote
2
down vote
$x,y$ are not uniquely defined. Let $a=2,b=1$. Then we could take $x=1, y=-1$, which makes your inequality false. Or we could take $x=-1.y=3$ which would make it true.
Note: In the comments, the OP has made clear that $x,y$ are intended to be the "minimal" solution, that is, the solution generated by the Euclidean Algorithm. In my example, the minimal solution is, of course, $x=0, y=1$ for which the claim holds. But even with this extra requirement, however, the general claim is false. For $a=3,b=2$, the minimal solution is $x=1,y=-1$, say.
answered Nov 13 at 0:55
lulu
37.8k24476
$x,y$ are not uniquely defined. Let $a=2,b=1$. Then we could take $x=1, y=-1$, which makes your inequality false. Or we could take $x=-1.y=3$ which would make it true.
Note: In the comments, the OP has made clear that $x,y$ are intended to be the "minimal" solution, that is, the solution generated by the Euclidean Algorithm. In my example, the minimal solution is, of course, $x=0, y=1$ for which the claim holds. But even with this extra requirement, however, the general claim is false. For $a=3,b=2$, the minimal solution is $x=1,y=-1$, say.
answered Nov 13 at 0:55
lulu
37.8k24476
edited Nov 13 at 10:49
answered Nov 13 at 0:55
lulu
37.8k24476
answered Nov 13 at 0:55
lulu
37.8k24476
answered Nov 13 at 0:55
lulu
37.8k24476
37.8k24476
probably worth mentioning that, if $a,b$ are positive, unless $a|b$ or $b|a,$ then one of $x,y$ is positive and the other negative.
– Will Jagy
Nov 13 at 0:58
@WillJagy Sure, though a priori the OP might imagine that, in that situation, we always needed $x<0, y>0$ (which, to be sure, we don't).
– lulu
Nov 13 at 0:59
Sorry, I was thinking about the Extended Euclidean algorithm. Are x, y uniquely defined in that?
– user5464854
Nov 13 at 1:09
@user5464854 Ah. The coefficients generated by Euclid are indeed well defined, in fact they are the "smallest" solutions. You can read more about that here.
– lulu
Nov 13 at 10:43
add a comment |
probably worth mentioning that, if $a,b$ are positive, unless $a|b$ or $b|a,$ then one of $x,y$ is positive and the other negative.
– Will Jagy
Nov 13 at 0:58
@WillJagy Sure, though a priori the OP might imagine that, in that situation, we always needed $x<0, y>0$ (which, to be sure, we don't).
– lulu
Nov 13 at 0:59
Sorry, I was thinking about the Extended Euclidean algorithm. Are x, y uniquely defined in that?
– user5464854
Nov 13 at 1:09
@user5464854 Ah. The coefficients generated by Euclid are indeed well defined, in fact they are the "smallest" solutions. You can read more about that here.
– lulu
Nov 13 at 10:43
probably worth mentioning that, if $a,b$ are positive, unless $a|b$ or $b|a,$ then one of $x,y$ is positive and the other negative.
– Will Jagy
Nov 13 at 0:58
probably worth mentioning that, if $a,b$ are positive, unless $a|b$ or $b|a,$ then one of $x,y$ is positive and the other negative.
– Will Jagy
Nov 13 at 0:58
@WillJagy Sure, though a priori the OP might imagine that, in that situation, we always needed $x<0, y>0$ (which, to be sure, we don't).
– lulu
Nov 13 at 0:59
@WillJagy Sure, though a priori the OP might imagine that, in that situation, we always needed $x<0, y>0$ (which, to be sure, we don't).
– lulu
Nov 13 at 0:59
Sorry, I was thinking about the Extended Euclidean algorithm. Are x, y uniquely defined in that?
– user5464854
Nov 13 at 1:09
Sorry, I was thinking about the Extended Euclidean algorithm. Are x, y uniquely defined in that?
– user5464854
Nov 13 at 1:09
@user5464854 Ah. The coefficients generated by Euclid are indeed well defined, in fact they are the "smallest" solutions. You can read more about that here.
– lulu
Nov 13 at 10:43
@user5464854 Ah. The coefficients generated by Euclid are indeed well defined, in fact they are the "smallest" solutions. You can read more about that here.
– lulu
Nov 13 at 10:43
add a comment |
1
This is a little confusing, since one of $x$ and $y$ must be negative if $a$ and $b$ are both positive.
– Ethan Bolker
Nov 13 at 0:56