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.

a) $$ 130x + 143y = 5957 $$
b) $$ 44x + 19y = 75 $$

the theorem says ax + by = c has solution if and only if d | c

however I work out both question with no solution as

a)

$$ 143 = 130 . 1 + 13 $$
$$ 130 = 13 . 10 + 0 $$

and 5957 is unable to be divided by 13 therefore no solution exists.

b)

$$ 44 = 19 . 2 + 6 $$
$$ 19 = 6 . 3 + 1 $$
$$ 6 = 3 . 2 + 0 $$

for b) I am unsure if there are any solution exists?

share|improve this question
    
Can you try to clean up your question please? It is hard for me to tell exactly what you are doing and what you are asking, without simply assuming that you are trying to apply Bezout's identity and getting stuck somewhere. –  Alex Becker May 1 '11 at 6:31

1 Answer 1

up vote 0 down vote accepted

Your first problem is correct.

Your second one, however, is not. When doing the Euclidean Algorithm, you mess up between your second and third steps. From $19 = 6*3 + 1$, you should go on the next next step $6 = 1*6 + 0$, indicating that 1 is the gcd of 19 and 44.

Let's also consider for a moment what your solution said: it said that either 2 or 3 divided both 44 and 19 (neither of which are correct). We also know that 19 is prime, so unless 44 is a multiple of 19 (which it isn't), they share no factors.

With that, it turns out that there are infinitely many solutions.

share|improve this answer
    
ops. mistake in b) for my euclidean algorithm. if 1 is the common divisor which means there are no common divisor? –  optimus May 1 '11 at 6:38
    
@liangteh: No, it means that 1 is the common divisor. –  mixedmath May 1 '11 at 6:43
    
in this case, for gcd = 1 how do I derive the general solution and particular solution? –  optimus May 1 '11 at 6:46
1  
@Liangteh: I will not do your homework for you, but I will do a quick example. Consider the numbers 3 and 8. $8 = 3*2 + 2$, and $3 = 2 * 1 + 1$. So 1 is the gcd. But then, by reversing my equations, I get that $1 = 3 - 2(1) = 3 - (8 - 3(2)) = 3*(3) - 8*(1)$. So I have a solution. –  mixedmath May 1 '11 at 6:52

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.