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?
Asked
Active
Viewed 72 times
0
-
1This is a little confusing, since one of $x$ and $y$ must be negative if $a$ and $b$ are both positive. – Ethan Bolker Nov 13 '18 at 00:56
1 Answers
2
$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.
lulu
- 70,402
-
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 '18 at 00: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 '18 at 00:59
-
Sorry, I was thinking about the Extended Euclidean algorithm. Are x, y uniquely defined in that? – user5464854 Nov 13 '18 at 01: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 '18 at 10:43