Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|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 mathoverflow.net/questions/32875 –  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.