1
$\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?

$\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
2
$\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 $d\le (a,b)$. But of course $d\ge (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)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.