MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $\{ a_i \}_{i=1}^N $ be a set of elements of the ring of integers, $\mathbb{Z}_D$ and define $g = \text{gcd}(a_1, a_2,\ldots, a_N, D)$. Then Bezout's Identity states that there exists another set $\{ x_i \}_{i=1}^N $ such that

$\sum_{i=1}^N a_i x_i \equiv g \bmod D$

For my work, I needed to show that such a solution set $\{ x_i \}_{i=1}^N $ exists with an ADDITIONAL requirement that $x_1$ must be coprime to $D$. I managed to prove this stronger version of Bezout's Identity using Chinese Remainder Representation (correctly I hope).

My question : Is this result well-known under another name? Do you know of any references discussing this result? Or is this a special case of an even stronger form of Bezout's Identity?

share|cite|improve this question
Presumably you can prove that a solution set exists with every $x_i$ coprime to $D$. I don't know that I've seen any mention of this in the literature - it just seems like the kind of thing a number theorist would mention, with a wave of the hands, if she needs it for something else. – Gerry Myerson Sep 6 '10 at 23:25
I don't think one can prove that there exists a solution set where every $x_i$ is coprime to $D$. I remember having a simple counterexample. – kett Sep 8 '10 at 14:16
@kett, you're right, e.g., if $2x+3y+5z\equiv1\pmod{30}$ and $y$ is odd then $z$ must be even. – Gerry Myerson Sep 10 '10 at 7:02
@kett, a version of your question was discussed in – Wadim Zudilin Oct 12 '10 at 6:30
@ Wadim, I'm having some difficulty seeing the connection. – kett Nov 10 '10 at 6:11

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.