Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

If I have Bézout coefficients (obtained using extended Euclidean algorithm) and one of them is negative, what is the easiest way to obtain positive Bézout coefficients?

share|improve this question
    
Could you give a little more detail? Do you have specific $a$ and $b$? –  rayradjr Nov 14 '12 at 18:44

2 Answers 2

up vote 2 down vote accepted

Given some natural $a$,$b$,$n$ we have the diophantine equation $$ax+by=n$$ which which we can find a solution for using Euclid's algorithm.

Let $(x,y)$ and $(x',y')$ be two distinct solutions then subtracting $ax+by=n$ and $ax'+by'=n$ we find $a(x-x')=b(y'-y)$. The question is what does this tell us about $x-x'$ and $y'-y$? It is difficult to deduce something from it since $a$ and $b$ are not coprime, so let $a' = \frac{a}{(a,b)}$, $b' = \frac{a}{(a,b)}$ and we have $a'(a,b)(x-x')=b'(a,b)(y'-y)$, now $a'|y'-y$ and $b'|x-x'$ so we must in fact have $y' = y + a'k$ and $x' = x-b'k$ for some integer $k$.

Reversing this, we can say that given any one solution $(x,y)$ we can parametrize all solutions by an integer $k$: $(x-b'k,y + a'k)$. If any positive solution to the diophantine equation exists, you can easily find it with this formula. If it doesn't you can use this formula to show that too.

share|improve this answer

Let $a,b,c$ be natural numbers. Can we solve $ax+by=c$ in naturals in a better way than using the euclidean algorithm? Obviously if $c < a+b$ we can't and if gcd(a,b) doesn't divide c we can't so lets suppose a,b,c coprime then we only really need to check if $y = (c-ax)/b$ is a positive integer for $1 \le x \le (c-b)/a$ as soon as its negative we can stop short knowing there are no solutions.

share|improve this answer

Your Answer

 
discard

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

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