This question already has an answer here:

I am looking for a general rule for all possible integers $k\in(a,b)$ such that $k$ is can be expressed as a linear combination of $a$ and $b$.

I understand that k must be a multiple of $\gcd(a,b)$, since any linear combination of $a$ and $b$ will be a multiple of $\gcd(a,b)$. Is there a general formula for $k$ in terms of $a,b$?

Thanks in advance!


marked as duplicate by davidlowryduda Oct 20 '17 at 13:01

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ The reverse is also true : all the multiples of $(a,b)$ are expressible as such a linear combination . This follows from Bézout's theorem . $\endgroup$ – user252450 Dec 21 '15 at 19:26
  • $\begingroup$ Could you elaborate what multiples of (a,b) mean? or did you mean gcd(a,b)? Because that's the answer I came up with too, as written in my answer below! $\endgroup$ – spandan madan Dec 21 '15 at 19:29
  • $\begingroup$ Yes , this is what I mean . Both notations are commonly used .It depends which you prefer . $\endgroup$ – user252450 Dec 21 '15 at 19:31
  • $\begingroup$ Thanks for your reply! Now know the formal reasoning for what I was thinking! $\endgroup$ – spandan madan Dec 21 '15 at 19:33

With a little bit of thinking, I was able to answer it myself. It is actually quite obvious.

Since we know that k must be a multiple of gcd(a,b), and that a and b both are multiples of gcd(a,b)-

let gcd(a,b) be g. so, k includes all integers - a,a+g,a+2g,a+3g......,b-g,b.

And these are all the possible values of k!


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