# Smallest positive integer that can be expressed as a linear combination of two integers

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?

• 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$. – John Omielan Dec 21 '18 at 3:20
• @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? – aesea Dec 21 '18 at 3:40
• A small correction to my comment is that the end should say "$x$ and $y$". – John Omielan Dec 21 '18 at 3:40
• 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. – John Omielan Dec 21 '18 at 3:47
• 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. – aesea Dec 21 '18 at 3:57

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)$$.